پوشش دوبخشی گراف $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*}