====== سوال ۷ ======


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

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

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

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


  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]