سوال ۷
یک درخت وزندار $T$ با راسهای ۱ تا $n$ داریم.
یک گراف $c$- رنگپذیر $H$ با راسهای ۱ تا $n$ داریم.
ثابت کنید افرازی از راسهای ۱ تا $n$ به $k$ مجموعه با شرایط زیر وجود دارد:
هیچ یالی از $H$ وجود نداشته باشد که هر دو سرش در یک مجموعه باشد.
اگر مجموع وزن یالهای $T$ را $X$ و مجموع وزن یالهای $T$ که هر دو سرشان در یک مجموعه است را $Y$ بنامیم داشته باشیم $2\times Y \times c \geq X$.