هر گراف کردال پوسته پذیر است.

Question

در قسمتی از اثبات قضیه گفته شده که د$ H_{m} $ dیک راس آزاد دارد و بنابراین هر فست از گراف $ \bigtriangleup ( \bar{G})$ اشتراکش با $ H_{m} $ دقیقا یک راس دارد.سوال من اینه که چرا دقیقا یک راس؟از برگ بودن $ H_{m}$وجود حداقل یک راس آزاد رو نتیجه میگیریم و نه فقط یک راس.

Answer 1

مشکل اینجاست که $ H_{m} $ یک فست در $G $ است ولی اشتراکش با فست های $ \triangle ( \overline{G}) $ را بررسی می کنیم

فرض حلف: فرض کنید $ H_{m} $ با یک فست از$ \triangle ( \overline{G}) $ بیش از یک نقطه اشتراک داشته باشد آنگاه این دو نقطه در یک فست $ \triangle ( \overline{G}) $ هستند و چون $ \triangle ( \overline{G}) $ مجتمع خوشه ای است لذا در $ \overline{G}$ این دو نقطه به هم وصل خواهند بود اما این در صورتی بود که این دو نقطه در $ H_{m} $ هم هستند لذا در $ G $ هم به هم وصل بودند که تناقض است.

پس بیش از یک راس نمیتواند باشد اما میدانیم که هر فست حداقل یک راس آزاد دارد. و این راس با فست های دیگر وصل نیست لذا در $ \overline{G} $ با تمام رئوس دیگر مجاور است پس هر فست در $ \triangle ( \overline{G}) $ این راس آزاد را دارد.