>>93
R(3, 4)≦9の証明：

1, 2, ..., R(3, 4)-1 を頂点とする完全グラフが色 1, 2 により、
色1 で塗られる K_3 および 色2 で塗られる K_4 をもたないように塗り分けられたと仮定する。

辺(1, i) (2≦i≦9) が色 j で塗られる i の集合を S_j (j=1, 2) と書く。

i, j∈S_1 ならば、仮定より (i, j) は色2 で塗られなければならない。
つまり、S_1 に属するの頂点同士を結ぶ辺は全て 色2 で塗られる。
色2 で塗られる K_4 をもたないから、|S_1|≦3 である。

ここで、|S_2|≧5を仮定する。

S_2に属する頂点から5つ選び 2, 3, 4, 5, 6 と再度記す。
色2 で塗られる K_4 をもたないから、ある辺 (たとえば (2, 3) )は色1で塗られなければならない。
同様に 3, 4, 5, 6 の二つを結ぶ辺の一つ (たとえば (3, 4) )は色1で塗られなければならない。

仮定より 2, 3, 4 の二つを結ぶ辺が全て色1で塗られることはないから、 (2, 4) は色2で塗られる。
(4, 5) が色2で塗られると、 1, 2, 4, 5 は色2で塗られる K_4 となる。よって (4, 5) は色1で塗られる。
上と同様に (3, 5) は色2で塗られ、 (5, 6) は色1で塗られることがわかる。

今、(4, 6) が色1で塗られていると仮定すると、4, 5, 6 は色1で塗られる K_3 となり、仮定に反する。
しかし (4, 6) が色2で塗られていると仮定すると 1, 2, 4, 6 は色2で塗られる K_4 となり、仮定に反する。

これにより、|S_1|≦3, |S_2|≦4 が示された。これは R(3, 4)-1≦1+3+4 、つまり R(3, 4)≦9 を与える。