第4問

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

ステップ 1/5: 二色補題を証明する

K_6\text{ with two edge colors}

詳しい解説

6頂点完全グラフを二色で彩色する。1頂点を選ぶと、そこから出る5辺の少なくとも3辺は同じ色（赤）で、頂点 $V_2,V_3,V_4$ へ向かう。