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

نیمه-دور دروی است که بتواند شامل ۱ راس هم باشد. یعنی هر دوی یک نیمه-دور است. و هر راس تکی هم یک نیمه-دور است.

در گراف $G$، $A$ یک «افراز راس‌های $G$ به نیمه-دور» است اگر و فقط اگر $A$ مجموعه‌ای از نیمه-دورهای $G$ باشد به صورتی که این نیمه-دورها در هیچ راسی با یکدیگر اشتراک نداشته باشند و هر راسی از $G$ حداقل در یکی از این نیمه‌-دورها آمده باشد.

گراف همبند لانه زنبوری $G$ داده شده است. تعداد «افراز‌های متفاوت را‌س‌های $G$ به نیمه-دور» را به صورت تابعی از تعداد راس‌ها و یال‌های آن به دست بیاورید و ادعای خود را اثبات کنید.

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