====== سوال ۶ ======

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

{{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۹:گراف:fasdfs.png |}}

ثابت کنید رئوس $G$‌ را می‌توان به دو بخش $V_1$ و $V_2$ افراز کرد به‌طوری‌که تعداد رئوس هر یک، حداکثر دو برابر تعداد رئوس دیگری باشد و زیرگراف القایی توسط هر یک نیز هم‌بند باشد.

  * [[سوال ۷|سوال بعد]]
  * [[سوال ۵|سوال قبل]]