$G$ یک گراف ساده‌ی بی‌جهت است.

$\chi_s(G)$ را این گونه تعریف می‌کنیم: کم‌ترین تعداد رنگی که با آن بتوان $G$ را رنگ‌آمیزی معتبر کرد، به صورتی که هیچ مسیر ۴-راسی دو رنگی در $G$ نباشد.

$a(G)$ را این‌گونه تعریف می‌کنیم: کم‌ترین تعداد رنگی که با آن بتوان $G$ را رنگ‌آمیزی معتبر کرد، به صورتی که هیچ دور دو رنگی در $G$ نباشد.

اثبات کنید: $a(G) \leq \chi_s(G) \leq a(G) \times 2^{a(G)-1}$

• سوال بعد
• سوال قبل