第4問

17人が互いに、各人が他の全員と郵便で文通している。手紙では3種類の話題だけが扱われ、各文通者の組はただ1つの話題を扱う。互いに同じ話題について書く3人が少なくとも存在することを証明せよ。

ステップ 4/5: 補題を適用する

K_6\text{ uses at most two colors if no edge has color 1}

詳しい解説

6頂点の間に色1の辺があれば、それは $V_1$ と色1の三角形を作る。なければ6頂点の完全グラフは残り二色だけなので、二色補題から単色三角形が得られる。