Diracの定理(Hamilton閉路)

定理が成り立たないとし、頂点数 $n\ge3$、$\delta(G)\ge n/2$ で Hamilton 閉路をもたない $G=(V,E)$ をとる。頂点集合が $V$ で $G$ の辺をすべて含み、Hamilton 閉路をもたないグラフのうち、辺の本数が最大のもの $H$ をとる（$G$ 自身がそのようなグラフなので、候補は空でない）。$H$ の次数は $G$ の次数以上なので $\delta(H)\ge n/2$ である。$n\ge3$ なので完全グラフ $K_n$ は Hamilton 閉路 $v_1,\dots,v_n,v_1$ をもち、$H\ne K_n$ である。そこで $H$ で隣接しない 2 頂点 $u,v$ をとる。
$H$ のとり方から $H+uv$ は Hamilton 閉路をもち、$H$ はもたないので、その閉路は辺 $uv$ を通る。閉路から辺 $uv$ を除くと、$H$ の Hamilton 路
$$ u=v_1,\ v_2,\ \dots,\ v_n=v $$
が得られる。添字の集合
$$ S:=\{\,i\mid 1\le i\le n-1,\ uv_{i+1}\in E(H)\,\},\qquad T:=\{\,i\mid 1\le i\le n-1,\ v_iv\in E(H)\,\} $$
を考える。$u$ 以外の頂点は $v_2,\dots,v_n$ なので $\lvert S\rvert=\deg_H(u)$、$v$ 以外の頂点は $v_1,\dots,v_{n-1}$ なので $\lvert T\rvert=\deg_H(v)$ である。
$S\cap T$ が元 $i$ をもつとする。$uv\notin E(H)$ なので $1\notin T$、$n-1\notin S$ であり、$2\le i\le n-2$ である。このとき
$$ v_1,\ v_2,\ \dots,\ v_i,\ v_n,\ v_{n-1},\ \dots,\ v_{i+1},\ v_1 $$
は、路の辺のほかに辺 $v_iv_n$（$i\in T$）と $v_{i+1}v_1$（$i\in S$）を使う $H$ の Hamilton 閉路であり、$H$ のとり方に反する。よって $S\cap T=\emptyset$ である。$S,T$ はどちらも $n-1$ 個の元からなる集合 $\{1,\dots,n-1\}$ に含まれるので
$$ \deg_H(u)+\deg_H(v)=\lvert S\rvert+\lvert T\rvert=\lvert S\cup T\rvert\le n-1 $$
である。一方 $\delta(H)\ge n/2$ より $\deg_H(u)+\deg_H(v)\ge n$ であり、矛盾する。$\square$

$v_0$ に隣接する頂点 $w$ が $P$ の上になければ、$w,v_0,v_1,\dots,v_k$ は長さ $k+1$ の道になり、$k$ の最大性に反する。よって $N(v_0)\subset\{v_1,\dots,v_k\}$ であり、同様に $N(v_k)\subset\{v_0,\dots,v_{k-1}\}$ である。とくに $d\le\deg(v_0)\le k$ なので $k\ge1$ である。
1 を示す。$k<2d$ とする。
（$k=1$ のとき）$N(v_0)\subset\{v_1\}$、$N(v_1)\subset\{v_0\}$ なので、辺 $v_0v_1$ はほかのどの頂点ともつながらない。$G$ は連結なので $V=\{v_0,v_1\}$、$n=2$ であり、$k=n-1$ である。
（$k\ge2$ のとき）まず、頂点の集合が $\{v_0,\dots,v_k\}$ に等しい閉路 $C$ があることを示す。$v_0v_k\in E$ なら $v_0,v_1,\dots,v_k,v_0$ が長さ $k+1\ge3$ の閉路である。$v_0v_k\notin E$ なら、
$$ S:=\{\,i\mid 0\le i\le k-1,\ v_0v_{i+1}\in E\,\},\qquad T:=\{\,i\mid 0\le i\le k-1,\ v_iv_k\in E\,\} $$
とおくと、上で見たことから $\lvert S\rvert=\deg(v_0)\ge d$、$\lvert T\rvert=\deg(v_k)\ge d$ であり、$S,T$ は $k$ 個の元からなる集合 $\{0,\dots,k-1\}$ に含まれる。$\lvert S\rvert+\lvert T\rvert\ge2d>k$ なので共通の元 $i$ がある。$v_0v_k\notin E$ より $0\notin T$、$k-1\notin S$ なので $1\le i\le k-2$ であり、
$$ v_0,\ \dots,\ v_i,\ v_k,\ v_{k-1},\ \dots,\ v_{i+1},\ v_0 $$
が求める閉路 $C$ である。
次に、$C$ がすべての頂点を通ることを示す。$C$ の外に頂点があるとすると、$G$ は連結なので、$C$ の頂点 $x$ と $C$ の外の頂点 $y$ を結ぶ辺 $xy$ がある。$C$ を $x$ から 1 周して $x$ の直前の頂点で止めると、$C$ の $k+1$ 個の頂点をすべて通る長さ $k$ の道が得られ、その先頭に $y$ を付けると長さ $k+1$ の道になって、$k$ の最大性に反する。よって $\{v_0,\dots,v_k\}=V$、$k=n-1$ である。$n\ge3$ なら $k=n-1\ge2$ でこの場合に当たり、$C$ は Hamilton 閉路である。
2 を示す。$k\ge2d$ ならよい。$k<2d$ なら 1 により $k=n-1$ である。どちらの場合も $k\ge\min\{n-1,2d\}$ である。$\square$

$n\ge3$、$\delta(G)\ge n/2$ とする。まず $G$ は連結である。実際、隣接しない相異なる 2 頂点 $u,v$ について、$N(u),N(v)$ は $n-2$ 個の元からなる集合 $V\setminus\{u,v\}$ に含まれ、$\lvert N(u)\rvert+\lvert N(v)\rvert\ge n>n-2$ なので、共通の隣接頂点がある。$d:=\delta(G)\ge n/2\ge1$ とおくと、最長の道の長さ $k$ は $k\le n-1< n\le2d$ をみたすので、thm-dirac-long-path の 1 により $G$ は Hamilton 閉路をもつ。$\square$

$n=1$ なら 1 頂点だけの長さ $0$ の道が Hamilton 路である。$n\ge2$ とする。$G$ に新しい頂点 $w$ を加え、$w$ と $G$ のすべての頂点を結んだグラフを $G'$ とする。$G'$ の頂点数は $n+1\ge3$ であり、$G$ の頂点 $v$ では $\deg_{G'}(v)=\deg_G(v)+1\ge\frac{n+1}2$、$w$ では $\deg_{G'}(w)=n\ge\frac{n+1}2$ である。thm-dirac-main により $G'$ は Hamilton 閉路をもつ。その閉路から $w$ と $w$ に接続する 2 本の辺を除くと、$G$ の $n$ 個の頂点をすべて通る道が残る。$\square$

$n=2$ なら $\delta(G)\ge1$ より $G$ は 1 本の辺からなり、その辺が完全マッチングである。$n\ge4$ なら thm-dirac-main により Hamilton 閉路 $v_1,\dots,v_n,v_1$ があり、$v_1v_2,\ v_3v_4,\ \dots,\ v_{n-1}v_n$ はどの頂点にもちょうど 1 本ずつ接続する辺の集合である。$\square$

$\lceil n/2\rceil-1$ は、$n=2m+1$ なら $m$、$n=2m$ なら $m-1$ であり、上の各グラフの最小次数はこれに等しい（$K_{p,q}$ の最小次数は $\min\{p,q\}$、貼り合わせたグラフでは共有した頂点の次数が $2m$、ほかの頂点の次数が $m$）。
部の大きさが異なる完全二部グラフは Hamilton 閉路をもたない。二部グラフの辺は 2 つの部の間を結ぶので、閉路をたどると頂点は 2 つの部に交互に属し、閉路の頂点のうち各部に属するものは同数になるからである（Hamilton閉路 の命題「二部グラフのHamilton閉路」）。
貼り合わせたグラフで共有した頂点を $w$ とする。Hamilton 閉路 $C$ があれば、$C$ から $w$ と $w$ に接続する 2 本の辺を除いたものは残りの $2m$ 頂点をすべて通る道であり、とくに $w$ を除いたグラフは連結である。しかし $w$ を除くと 2 つの $K_m$ に分かれて連結でない。$\square$