در کشور خیکولند $n$ شهر وجود دارد و قرار است $n-1$ شرکت هواپیمایی $T_1$, $T_2$, $\cdots$, $T_{n-1}$, برقراری ارتباط هوایی بین این شهرها را به عهده بگیرند. در ضمن میدانیم شرکت $T_i$ قرار است مدیریت $i$ خط هوایی را به عهده بگیرد (هر خط هوایی ارتباط دو شهر را در دو جهت رفت و برگشت پوشش میدهد). همچنین میدانیم شرکت $T_i$ برای انتخاب $i$ خط هوایی خود یکی از دو الگوی زیر را در نظر گرفته است:
ثابت کنید الگوهای انتخابی شرکتها هر طور باشند میتوان ارتباط هوایی شهرها را بین این شرکتها طوری تقسیمبندی کرد که بین هر دو شهر, دقیقاً یک خط هوایی برقرار باشد.