◆ わからない問題はここに書いてね ２４７ ◆

>>510
R(3,4)≦9 であること。
9 個の頂点を持つ完全グラフの辺を赤と青に塗り分けて、赤い辺からなる 3 頂点の完全グラフも青い辺からなる 4 頂点の完全グラフもないようにできたとして矛盾を導く。

1) どの頂点からも赤い辺は 4 本以上出ることはない。
2) どの頂点からも青い辺は 6 本以上出ることはない。
3) したがって、どの頂点からも赤い辺が 3 本、青い辺が 5 本出ている。
4) 赤い辺の総数×2=3×9 となり左辺は偶数、右辺は奇数だから矛盾。