§E13.7Hamilton 閉路

証明.$n\ge3$を固定し、$\lvert V\rvert=n$である集合$V$を固定する。Ore の条件を満たしながら Hamilton 閉路をもたない$V$上の有限単純無向グラフが存在すると仮定する。$V$上の単純グラフは辺集合が$V$の二元部分集合の集合の部分集合として定まるので有限個であり、そのようなグラフの全体は空でない有限集合である。ゆえに、そのうち辺数が最大のものを一つ取ることができる。これを$G=(V,E)$とする。

隣接しない二頂点の存在.$G$は完全グラフではない。実際、$V$の頂点を任意に$y_1,\dots,y_n$と並べると、完全グラフでは$y_iy_{i+1}$と$y_ny_1$がすべて辺であるから、$n\ge3$より$y_1,\dots,y_n,y_1$は Hamilton 閉路になる。これは$G$が Hamilton 閉路をもたないことに反する。ゆえに$u\ne v$かつ$uv\notin E$を満たす$u,v\in V$が存在する。

辺を一本加える.$G^{+}=(V,E\cup\{uv\})$と置く。$G^{+}$も Ore の条件を満たす。実際、$G^{+}$で隣接しない相異なる二頂点$y,z$は$G$でも隣接せず、辺を加えても次数は減らないので$\deg_{G^{+}}(y)+\deg_{G^{+}}(z)\ge\deg_{G}(y)+\deg_{G}(z)\ge n$が成り立つ。$G^{+}$の辺数は$G$の辺数より$1$大きいので、$G$の取り方より$G^{+}$は Hamilton 閉路をもたないグラフではない。すなわち$G^{+}$は Hamilton 閉路$H$をもつ。

Hamilton 道を取り出す.$H$は辺$uv$を通る。実際、$H$が辺$uv$を通らなければ$H$の辺はすべて$E$に属し、$H$は$G$の Hamilton 閉路になって、$G$が Hamilton 閉路をもたないことに反する。$H$から辺$uv$を取り除くと、$G$における$u$から$v$への Hamilton 道が得られる。これを$u=x_1,\ x_2,\ \dots,\ x_n=v$と書く。$x_1,\dots,x_n$は$V$の頂点をちょうど一度ずつ尽くし、$1\le i\le n-1$について$x_ix_{i+1}\in E$である。

二つの添字集合. 次の集合を定める。$I=\{i:\ 2\le i\le n,\ x_1x_i\in E\},\qquad J=\{i:\ 2\le i\le n,\ x_{i-1}x_n\in E\}.$

写像$i\mapsto x_i$は$\{2,\dots,n\}$から$V\setminus\{x_1\}$への全単射であり、$x_1$に隣接する頂点は$V\setminus\{x_1\}$に属する。ゆえに§D2.2 命題 1.5より$\lvert I\rvert=\deg_G(x_1)=\deg_G(u)$である。同様に、写像$i\mapsto x_{i-1}$は$\{2,\dots,n\}$から$V\setminus\{x_n\}$への全単射であるから$\lvert J\rvert=\deg_G(x_n)=\deg_G(v)$である。

共通の添字の存在.$u$と$v$は$G$で隣接しないから、Ore の条件より$\lvert I\rvert+\lvert J\rvert=\deg_G(u)+\deg_G(v)\ge n$である。一方$I\cup J\subseteq\{2,\dots,n\}$であり、$\lvert\{2,\dots,n\}\rvert=n-1$である。もし$I\cap J=\varnothing$ならば§D2.2 定理 2.1より$\lvert I\rvert+\lvert J\rvert=\lvert I\cup J\rvert\le n-1<n$となって矛盾する。ゆえに$I\cap J\ne\varnothing$であり、$i\in I\cap J$を一つ取ることができる。

この$i$は$2$ではない。実際、$2\in J$とすると$x_{1}x_n\in E$、すなわち$uv\in E$となり、$u$と$v$が隣接しないことに反する。ゆえに$3\le i\le n$である。

閉路の構成. 頂点列$x_1,\ x_2,\ \dots,\ x_{i-1},\ x_n,\ x_{n-1},\ \dots,\ x_i,\ x_1$を考える。この列に現れる頂点は$x_1,\dots,x_{i-1}$と$x_i,\dots,x_n$であり、あわせて$V$のすべての頂点をちょうど一度ずつ尽くす。連続する対がいずれも$E$に属することを確かめる。

• $1\le j\le i-2$に対する対$x_jx_{j+1}$は Hamilton 道の辺であるから$E$に属する。
• 対$x_{i-1}x_n$は$i\in J$であることから$E$に属する。
• $i\le j\le n-1$に対する対$x_{j+1}x_j$は Hamilton 道の辺$x_jx_{j+1}$と同じであるから$E$に属する。列$x_n,x_{n-1},\dots,x_i$はこれらの対を逆順にたどったものである。
• 対$x_ix_1$は$i\in I$であることから$E$に属する。

現れる対は$(i-2)+1+(n-i)+1=n$個であり、$n\ge3$であるから、この列は$G$の Hamilton 閉路である。これは$G$が Hamilton 閉路をもたないことに反する。

以上より仮定は誤りであり、$n\ge3$かつ Ore の条件を満たす有限単純無向グラフはすべて Hamilton 閉路をもつ。▨

証明.$G$が Ore の条件を満たすことを示す。$u\ne v$かつ$uv\notin E$を満たす$u,v\in V$を任意に取る。最小次数の定義より$\deg_G(u)\ge\delta(G)$かつ$\deg_G(v)\ge\delta(G)$であるから$\deg_G(u)+\deg_G(v)\ge2\delta(G)\ge2\cdot\frac n2=n$が成り立つ。隣接しない相異なる二頂点が存在しない場合、Ore の条件は空虚に成り立つ。いずれの場合も$G$は Ore の条件を満たすから、定理 2.1より$G$は Hamilton 閉路をもつ。▨