§C5.5競技数学：グラフ・離散構造

頂点全体の集合を、次数が奇数の頂点の集合$V_{\mathrm{odd}}$と、次数が偶数の頂点の集合$V_{\mathrm{even}}$に分ける。握手補題により

であり、右辺は偶数である。左辺の第2項は偶数の和であるから偶数であり、したがって第1項$\displaystyle\sum_{v\in V_{\mathrm{odd}}}d(v)$も偶数である。この和は$|V_{\mathrm{odd}}|$個の奇数の和であり、奇数を$m$個足した和の偶奇は$m$の偶奇に等しい。よって$|V_{\mathrm{odd}}|$は偶数である。▨

6人を頂点とし、どの2人の間にも辺を引いて、知り合いである2人を結ぶ辺を赤、知り合いでない2人を結ぶ辺を青に塗る。互いに知り合いである3人は3辺がすべて赤の三角形に、互いに知らない3人は3辺がすべて青の三角形に対応する。

1人$v$を選ぶ。$v$から他の5人へ出る5本の辺は赤と青の2色に塗られているので、鳩の巣原理により、同じ色の辺が3本以上ある。その色を赤として議論する（青の場合は、以下の議論で赤と青を入れ替える）。$v$と赤の辺で結ばれた3人を$a,b,c$とする。

$a,b,c$のうちのある2人を結ぶ辺が赤なら、その2人と$v$の3人を結ぶ3辺はすべて赤であり、互いに知り合いである3人が得られる。そうでなければ、$a,b,c$のどの2人を結ぶ辺も青であり、$a,b,c$は互いに知らない3人である。いずれの場合も、求める3人が存在する。▨

最大値は$16$である。

上からの評価を、本文で三角形を含まないグラフの辺数を評価した方法と同じ方法で、$n=8$について行う。三角形を含まない頂点数8の単純グラフの辺数を$m$とする。辺$uv$を一つ取る。$u$に隣接する頂点のうち$v$以外のものは$d(u)-1$個、$v$に隣接する頂点のうち$u$以外のものは$d(v)-1$個あり、どちらも$u,v$以外の6個の頂点のうちにある。共通の頂点$w$があれば、$u,v,w$は三角形をなすので、共通の頂点はない。したがって$(d(u)-1)+(d(v)-1)\le6$、すなわち$d(u)+d(v)\le8$である。この不等式をすべての辺について足すと、各頂点$v$の次数$d(v)$は$v$を端点とする$d(v)$本の辺で一回ずつ現れるので

である。一方、握手補題$\sum_{v}d(v)=2m$を用いると

であるから、$\dfrac{m^2}2\le\sum_{v}d(v)^2\le8m$である。$m>0$なら両辺を$m$で割って$m\le16$を得る。$m=0$でも$m\le16$である。

等号が成り立つグラフとして、8頂点を4頂点ずつの組$X,Y$に分け、$X$の各頂点と$Y$の各頂点を辺で結び、組の中には辺を置かないグラフ（完全二部グラフ$K_{4,4}$）を取る。辺数は$4\times4=16$である。どの3頂点を選んでも、そのうちの2頂点は同じ組に属し、辺で結ばれていないので、このグラフは三角形を含まない。したがって、辺数の最大値は$16$である。▨

辺は同じ連結成分の頂点どうしを結ぶので、各連結成分を辺の両端が異なる色になるように赤と青で塗ることができれば、グラフ全体も同じ条件で塗ることができる。そこで、奇閉路を含まない連結なグラフ$G$について示す。

頂点$r$を一つ選び、各頂点$x$について、$r$と$x$を結ぶ道の長さの最小値を$\delta(x)$とする。$G$は連結であるから$\delta(x)$は定まる。$\delta(x)$が偶数の頂点を赤、奇数の頂点を青に塗る。

辺$xy$の両端が異なる色であることを示す。$r$から$x$への長さ$\delta(x)$の道に辺$xy$を加えると$y$へ至る長さ$\delta(x)+1$の経路が得られるので$\delta(y)\le\delta(x)+1$であり、同様に$\delta(x)\le\delta(y)+1$である。両端が同じ色であると仮定すると、$\delta(x)$と$\delta(y)$は偶奇が等しく、差が$1$以下であるから、$\delta(x)=\delta(y)=k$である。

$r$から$x$への長さ$k$の道を$P$、$r$から$y$への長さ$k$の道を$Q$とする。$P$の頂点を$r=p_0,p_1,\ldots,p_k=x$、$Q$の頂点を$r=q_0,q_1,\ldots,q_k=y$と書く。$P,Q$はともに最短の道であるから、$p_i$と$q_i$はどちらも$\delta$の値が$i$の頂点である。実際、$r$から$p_i$までの$P$の部分は長さ$i$の道であるから$\delta(p_i)\le i$であり、$\delta(p_i)<i$なら$x$へ至る長さ$k$未満の経路が得られて$\delta(x)=k$に反する。$q_i$についても同じである。

$P$と$Q$に共通する頂点のうち、$P$での番号が最大のものを$p_j$とする（$p_0=q_0=r$が共通なので存在する）。$\delta(p_j)=j$であり、$Q$の頂点で$\delta$の値が$j$のものは$q_j$だけであるから、$p_j=q_j$である。番号が$j$より大きい$P$の頂点は$Q$に現れない。また、番号が$j$より大きい$Q$の頂点$q_i$が$P$に現れるなら、$\delta$の値を比べるとそれは$p_i$であり、$i>j$は$j$の最大性に反する。したがって、$p_j,p_{j+1},\ldots,p_k$と$q_{j+1},\ldots,q_k$は相異なる頂点である。$x\ne y$であるから$j<k$である。

すると、$p_j$から$P$に沿って$x$へ進み、辺$xy$を通り、$Q$を逆にたどって$q_j=p_j$へ戻る閉路が得られる。この閉路の長さは$(k-j)+1+(k-j)=2(k-j)+1$で奇数であり、$k-j\ge1$から$3$以上である。これは$G$が奇閉路を含まないことに反する。よって辺の両端は異なる色であり、$G$は二部グラフである。▨