در گراف $G$ زیر درخت‌های نه لزوما فراگیر $T_1,…,T_k$ مشخص شده‌اند. می‌خواهیم برای هر درخت یک یال به عنوان نماینده‌اش انتخاب کنیم به‌طوری‌که با هم متفاوت باشند و جمعا تشکیل یک جنگل بدهند. ثابت کنید شرط لازم و کافی برای انجام این کار این است که به ازای هر تعدادی از این درخت‌ها مثلا $r$ درخت $T_{i_1},…,T_{i_r}$ داشته باشیم $p\geq q+r$ که $p$ تعداد راس‌ها و $q$ تعداد مولفه‌های همبندی گراف حاصل از $T_{i_1} \cup … \cup T_{i_r}$ است.

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