ラムゼー理論

$K_6$ の1頂点は $5$ 個の隣接頂点を持ち、それを $2$ 色に分けると少なくとも $3$ 個が同じクラスに入る。その $3$ 頂点間に同色の辺が1本でもあればそれで三角形ができ、なければ逆の色の三角形ができる。

**ステップ1(上界 $R(3,3) \le 6$)。** $K_6$ の任意の頂点 $v$ をとる。v に接続する $5$ 本の辺は赤または青に塗られている。鳩の巣原理($\lceil 5/2 \rceil = 3$)により、少なくとも $3$ 本の辺が同じ色を持つ——辺 $vu_1, vu_2, vu_3$ がすべて赤であるとする。

**ステップ2($\{u_1, u_2, u_3\}$ での場合分け)。** 三角形 $\{u_1, u_2, u_3\}$ の内部の $3$ 本の辺を見る。もしそのうち1本——例えば $u_1u_2$——が赤なら、$\{v, u_1, u_2\}$ が赤の $K_3$ をなす。そうでなければ $3$ 本の辺 $u_1u_2, u_2u_3, u_3u_1$ はすべて青であり、$\{u_1, u_2, u_3\}$ 自身が青の $K_3$ をなす。

**ステップ3(下界 $R(3,3) > 5$)。** $K_5$ の頂点を $\mathbb{Z}/5\mathbb{Z}$ でラベル付けする。$i - j \equiv \pm 1 \pmod 5$ のとき辺 $ij$ を赤、$i - j \equiv \pm 2 \pmod 5$ のとき青に塗る。どちらの色クラスも三角形を含まない $5$ 長サイクルをなし、$R(3,3) > 5$、ゆえに $R(3,3) = 6$ が示された。

頂点 $v$ を固定すると、その赤近傍が十分大きくて赤の $K_{s-1}$ または青の $K_t$ を含むか、さもなくば青近傍が十分大きくて赤の $K_s$ または青の $K_{t-1}$ を含む。

**ステップ1($v$ の近傍の鳩の巣分割)。** $N = R(s - 1, t) + R(s, t - 1)$ とおき、頂点 $v \in V(K_N)$ を固定する。残りの $N - 1$ 頂点を $V_R$($v$ への赤辺)と $V_B$($v$ への青辺)に分ける。$|V_R| + |V_B| = R(s - 1, t) + R(s, t - 1) - 1$ なので、$|V_R| \ge R(s - 1, t)$ または $|V_B| \ge R(s, t - 1)$ が成り立つ。

ステップ2(帰納的結論)。 $|V_R| \ge R(s - 1, t)$ ならば、$V_R$ 上の部分グラフは青の $K_t$、または $v$ と合わせて赤の $K_s$ をなす赤の $K_{s-1}$ を含む。$V_B$ についても対称的に成り立つ。

ステップ3(帰納法による二項係数上界)。 基底 $R(2, t) = t$ と $R(s, 2) = s$ は $\binom{t}{1}$ と $\binom{s}{s-1}$ に一致する。$s, t \ge 3$ のときパスカルの恒等式により $R(s, t) \le \binom{s + t - 3}{s - 2} + \binom{s + t - 3}{s - 1} = \binom{s + t - 2}{s - 1}$ となる。