قضیه کوراتوسکی

قضیه کوراتوسکی

یک گراف نامسطح است، اگر و فقط اگر شامل زیرگرافی همومورفیک با K3,3 یا K5 باشد. مشاهده کردیم که K3,3 و K5 مسطح نیست. اگر گرافی شامل یکی از این دو گراف به عنوان زیرگراف باشد، مسطح نیست. به‌طور شگفت‌آوری تمام گراف‌های نامسطح باید شامل زیرگرافی باشند که با استفاده از عملیات مجاز خاص از K3,3 و K5 به دست می‌آید.

اگر گرافی، مسطح باشد، هر گرافی که از حذف یال {u,v} و اضافه کردن راس جدید w به همراه یال‌های {w,u} و {u,w} به دست می‌آید، نیز مسطح خواهد بود.

به چنین عملی زیر تقسیم مقدماتی گفته می‌شود.

گراف‌های G1=(V1,E1) و G2=(V2,E2) همومورفیک نامیده می‌شوند، اگر بتوان آن‌ها را از یک گراف یکسان، با دنباله‌ای از زیرتقسیم‌های مقدماتی به دست آورد.

(شکل گراف‌های همومورفیک)

ریاضی‌دان هلندی کازیمیرز کوراتوسکی در سال ۱۹۳۰ قضیه ۲ را که گراف‌های مسطح را با استفاده از مفهوم همومورفیسم توصیف می‌کند، بیان کرد.

قضیه ۲: یک گراف نامسطح است، اگر و فقط اگر شامل زیرگرافی باشد که با K3,3 یا K5 همومورفیک است.

واضح است که یک گراف شامل زیرگرافی همومورفیک با K3,3 یا K5 غیر مسطح است؛ ولی عکس آن این که هر گراف غیر مسطح شامل زیر گرافی همومورفیک با K3,3 یا K5 است، پیچیده بوده و در اینجا مطرح نخواهد شد.

منابع

ریاضیات گسسته / تألیف کنت. اچ. روزن