ایلیچ یک دایره دارد که $n$ نقطه با فواصل مساوی روی محیط آن قرار گرفته‌اند. او هم‌چنین تعدادی از وترهای میان نقاط را کشیده است.

هر وتر را به طور مستقل در نظر بگیرید. این وتر دایره را به دو قسمت تقسیم می‌کند. ایلیچ یکی از این قسمت‌ها را طرف سلطانی وتر و قسمت دیگر را طرف جبلی وتر قرار می‌دهد.

به زیرمجموعه‌ای $k$ عضوی از وترها برانکویی گوییم، اگر دو شرط زیر را داشته باشند:

• اجتماع مجموعه‌ی نقاط انتهایی وترها شامل $2k$ عضو باشد.
• وترها را به دل‌خواه با ۱ تا $k$ شماره‌گذاری می‌کنیم. $2k$ نقطه‌ی گفته شده در شرط یکم، $2k$ کمان کوچک دور دایره می‌سازند. به هر کمان یک رشته‌ی دودویی $k$ رقمی نسبت می‌دهیم، به این صورت که اگر کمان گفته شده در طرف سلطانی وتر $i$ بود، رقم $i$ ام را ۰ و در غیر این صورت رقم $i$ ام را ۱ قرار می‌دهیم. شرط دوم این است که تمام $2k$ رشته‌ی دودویی ساخته شده توسط کمان‌ها متمایز باشند.

1. زیرمجموعه‌ای از وترها را در نظر بگیرید که شرط یکم برانکویی بودن را دارند. گراف نیمایی این وترها، گرافی است که هر رأس آن متناظر یکی از وترهاست و رأس‌های دو وتر را به هم وصل می‌کنیم، اگر با هم تقاطع داشته باشند. ثابت کنید شرط دوم برانکویی بودن زیرمجموعه معادل این است که گراف نیمایی آن همبند باشد. (۲۰ نمره)
2. فرض کنید هیچ ۱۳۹۷ وتر برانکویی نداریم. ثابت کنید تعداد وترها از $O(n)$ است. (۸۰ نمره)

• سوال قبل