مسأله ۲

برای $n$ های کوچک‌تر حکم را ثابت کنید.

اگر حکم در مورد گراف کامل $n$ راسی باشد، نشان دهید حداقل به $\lceil \frac{3n}{4} \rceil$ رنگ نیاز داریم.

برای این کار، از استقرای ریاضی استفاده کنید.

اگر رنگی فقط مرکز یک ستاره باشد، می‌توان آن راس را حذف کرد و طبق فرض استقرا، حکم صحت خواهد داشت.

گرافی جدید مثل $G'$ بسازید که راس‌های آن با راس‌های گراف کامل داده شده یکی باشد. بین هر دو راس که مرکز ستاره‌های هم‌رنگ هستند، یال بگذارید.

پیشتر نشان دادید راس تنها در این گراف نیست. نشان دهید مؤلفه‌ای نمی‌تواند دقیقا یک یال داشته باشد

برای این کار، یال بین دو مرکز را لحاظ کنید. فرض کنید این یال بین مرکز دو ستاره‌ی آبی باشد.

پیرو راهنمایی بالا، دقت کنید این یال هیچ رنگی غیر از آبی نمی‌تواند داشته باشد.

ثابت کنید هیچ مؤلفه‌ای به شکل مسیر به طول ۲ نخواهد بود

برای این کار، فرض کنید دو راس $a$ و $b$ مرکز ستاره‌های آبی، و دو راس $b$ و $c$ مرکز ستاره‌های قرمز باشند. روی یال‌های $ab$، $bc$ و $ac$ حالت‌بندی کنید.

یال $ab$ نمی‌تواند آبی و یال $bc$ نمی‌تواند قرمز باشند. پس به ترتیب، قرمز و آبی هستند.

اگر یال $ac$ قرمز باشد، راس $a$ برگی از ستاره‌ی قرمز $c$ و برگی از ستاره‌ی قرمز $b$ خواهد بود.

برای مثال، راس‌ها را به دسته‌های چهار راسه افراز کنید. راس‌های دسته‌ی $i$ ام را $a_i$، $b_i$، $c_i$ و $x_i$ بنامید. رنگ‌های $A_i$، $B_i$ و $C_i$ را برای این چهار راس نام‌گذاری می‌کنیم.

سعی کنید طوری مثال بسازید که مرکز ستاره‌های رنگ $A_i$ راس‌های $a_i$ و $x_i$، مرکز ستاره‌های رنگ $B_i$ راس‌های $b_i$ و $x_i$ و مرکز ستاره‌های رنگ $C_i$ راس‌های $c_i$ و $x_i$ باشند.

در بین چهار راس هر دسته، رنگ‌آمیزی را چنین انجام دهید: $$a_ib_i,x_ic_i → A_i$$ $$ b_ic_i,x_ia_i → B_i$$ $$ c_ia_i, x_ib_i → C_i$$

برای یال‌های بین دو دسته با شماره‌های $i$ و $j$ که $i<j$ قانون رنگ‌آمیزی ارائه دهید.

برخی قوانین کمک کننده به شرح زیر هستند: $$a_ia_j, a_ib_j, a_ic_j → A_i$$ $$a_ix_j → A_j$$

برخی قوانین کمک‌کننده‌ی دیگر: $$b_ia_j, b_ib_j, b_ic_j, b_ix_j→B_i$$

برخی قوانین کمک کننده‌ی دیگر: $$c_ia_j, c_ib_j, c_ic_j, c_ix_j → C_i$$

یال‌های پایانی: $$x_ia_j→A_j$$ $$x_ib_j→B_j$$ $$x_ic_j→C_j$$ $$x_ix_j→A_i$$