چرا مسطح نبودن یک گراف هم ارز با داشتن زیرگرافی همریخت با $K_5$ یا $K_{3,3}$ است؟

Question

قضیه کوراتوفسکی: یک گراف غیرمسطح است اگر و فقط اگر شامل یک زیرگراف همسان ریخت با گراف k3,3 یا گراف k۵ باشد.

Comments

@Omid777 اصلا شروع به جستجو در کتاب‌های مرتبط کردید؟ یا حتی یک جستجوی ساده در اینترنت؟ من به پرسش شما برچسب «درخواست مرجع» را افزودم چون این قضیه چیزی هست که به راحتی در کتاب‌های زیادی پیدا می‌شود.

Answer 1

قضیهٔ کوراتوفسکی، قضیهٔ ۱۰ فصل ۹، صفحهٔ ۲۰۲ کتاب «نظریهٔ گراف‌ها و کاربردهای آن»، نوشتهٔ «جی. ای. باندی» و «یو. اس. آر. مورتی»، ترجمهٔ «حمید ضرّابی‌زادی»، چاپ «مؤسسهٔ فرهنگی هنری دیباگران تهران»، چاپ ۱۳۷۸، است که اثباتش نیز در همان جا آمده‌است.