پوشش دوبخشی گراف ‎$G$‎، مجموعه‌ای از زیرگراف‌های دوبخشی آن است که هر یال از ‎$G$‎ حداقل در یکی از آن‌ها آمده باشد. وزن این پوشش برابر با مجموع تعداد رئوس این زیرگراف‌ها است. فرض کنید ‎$bc(G)$‎ کوچکترین عددی باشد که یک پوشش دوبخشی از ‎$G$‎ با آن وزن موجود باشد.

1. ثابت کنید ‎$bc(K_{2^n})\leq 2^n.n$
2. ثابت کنید ‎$bc(K_{2^n})\geq 2^n.n$

یادآوری: برای این بخش شاید مجبور به استفاده از نابرابری حسابی-هندسی شوید. طبق این نامساوی برای اعداد مثبت ‎$a_1,\ldots,a_n$‎ داریم: ‎ $$\begin{equation*}‎ ‎\frac{\sum_{i=1}^n a_i}{n} \geq \sqrt[n]{\Pi_{i=1}^n a_i}‎ ‎\end{equation*}$$ ‎

• سوال قبل