第4問

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

ステップ 3/5: 同色の隣接点6個を選ぶ

\left\lceil\frac{16}{3}\right\rceil=6

詳しい解説

人の各組をその話題の色で彩色する。任意の $V_1$ から出る16辺は3色なので、少なくとも6辺は同じ色（色1）である。