یک درخت وز‌ن‌دار $T$ با راس‌های ۱ تا $n$ داریم.

یک گراف $c$- رنگ‌پذیر $H$ با راس‌های ۱ تا $n$ داریم.

ثابت کنید افرازی از راس‌های ۱ تا $n$ به $k$ مجموعه با شرایط زیر وجود دارد:

1. هیچ یالی از $H$ وجود نداشته باشد که هر دو سرش در یک مجموعه باشد.
2. اگر مجموع وزن یال‌های $T$ را $X$ و مجموع وزن یال‌های $T$ که هر دو سرشان در یک مجموعه است را $Y$ بنامیم داشته باشیم $2\times Y \times c \geq X$.

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