یک درخت $T$ به ما داده شده است. هر راس از این درخت یک زیرمجموعه به اندازه حداکثر $k$ از $\{1,2,…,n\}$ را داراست. برای هر $i$، راس‌هایی از $T$ که در مجموعه‌شان عدد $i$ را دارند، یک زیرگراف همبند (زیردرخت) را تشکیل می‌دهند. حال گراف $G$ با راس‌های $1,2,…,n$ را به این صورت می‌سازیم که اگر دو عدد $i$ و $j$ باهم در مجموعه‌ی حداقل یک راس از $T$ آمده باشند، در گراف $G$ بینشان یال می‌گذاریم.(اگر دو عدد در یک مجموعه آمده باشند حتما بینشان در گراف $G$ یال می‌گذاریم).

ثابت کنید گراف $G$ $k$-رنگ پذیر است.

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