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

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})$ این راس آزاد را دارد.