§E16.7Hamilton 閉路

(1)を示す。$G=(V,E)$を$\lvert V\rvert=n$、$\lvert E\rvert\ge\binom{n-1}{2}+2$の有限単純無向グラフとし、$u\ne v$かつ$uv\notin E$を満たす$u,v\in V$を任意に取る。$E$の各辺は、$u$と$v$の少なくとも一方を端点にもつか、どちらも端点にもたないかのいずれかである。$u$と$v$は隣接しないので、$u$と$v$の両方を端点にもつ辺は存在しない。したがって§D2.2 定理 2.1より、$u$と$v$の少なくとも一方を端点にもつ辺の本数は$\deg_G(u)+\deg_G(v)$である。どちらも端点にもたない辺は$V\setminus\{u,v\}$の二元部分集合であるから、§D2.2 命題 3.1よりその本数は$\binom{n-2}{2}$以下である。ゆえに

である。

であるから、$\deg_G(u)+\deg_G(v)\ge(n-2)+2=n$を得る。隣接しない相異なる二頂点が存在しない場合、Ore の条件は空虚に成り立つ。いずれの場合も$G$は Ore の条件を満たすから、定理 2.1より$G$は Hamilton 閉路をもつ。

例を構成する。$V=\{1,2,\dots,n\}$とし、$\{1,\dots,n-1\}$の二元部分集合の全体に辺$\{1,n\}$を加えたものを$E$とする。§D2.2 命題 3.1より$\lvert E\rvert=\binom{n-1}{2}+1$であり、頂点$n$に隣接する頂点は$1$だけであるから$\deg(n)=1$である。$G=(V,E)$が Hamilton 閉路$y_1,y_2,\dots,y_n,y_1$をもつと仮定し、$y_k=n$とする。閉路の列で$y_k$の直前と直後に現れる頂点（$k=1$のときは$y_n$と$y_2$、$k=n$のときは$y_{n-1}$と$y_1$、それ以外のときは$y_{k-1}$と$y_{k+1}$）は、いずれも$y_k$と辺で結ばれる。$n\ge3$であり$y_1,\dots,y_n$は相異なるので、この二頂点は相異なる。したがって$\deg(n)\ge2$となり、$\deg(n)=1$に反する。ゆえに$G$は Hamilton 閉路をもたない。前半の結果とあわせると、$n$頂点の有限単純無向グラフで Hamilton 閉路をもたないものの辺数の最大値は$\binom{n-1}{2}+1$である。

(2)を示す。$u\ne v$かつ$uv\notin E$を満たす$u,v\in V$に対し、$A_u=\{w\in V:\ uw\in E\}$、$A_v=\{w\in V:\ vw\in E\}$と置く。$\lvert A_u\rvert=\deg_G(u)$、$\lvert A_v\rvert=\deg_G(v)$である。$G$は単純グラフであるから$u\notin A_u$であり、$uv\notin E$であるから$v\notin A_u$である。同様に$u,v\notin A_v$である。ゆえに$A_u\cup A_v\subseteq V\setminus\{u,v\}$であり、$\lvert A_u\cup A_v\rvert\le n-2$である。$A_u\cup A_v$は互いに素な$A_u$と$A_v\setminus A_u$の合併であり、$A_v$は互いに素な$A_u\cap A_v$と$A_v\setminus A_u$の合併であるから、§D2.2 定理 2.1より

である。$\deg_G(u)+\deg_G(v)\ge n$ならば右辺は$2$以上であり、$A_u\cap A_v$の元、すなわち$u$と$v$の両方に隣接する頂点が少なくとも二つ存在する。

次に、隣接しない任意の相異なる二頂点$u,v$について$\deg_G(u)+\deg_G(v)\ge n-1$が成り立つとする。相異なる$x,y\in V$を任意に取る。$xy\in E$ならば、$x,y$は$x$から$y$への歩道である。$xy\notin E$ならば、上の不等式を$u=x$、$v=y$に適用して$\lvert A_x\cap A_y\rvert\ge(n-1)-(n-2)=1$を得るので、$x$と$y$の両方に隣接する頂点$w$が存在し、$x,w,y$は$x$から$y$への歩道である。いずれの場合も$y$は$x$から到達可能であるから、§D2.7 定義 2.3より$G$は連結である。この議論により、相異なる二頂点は長さ$2$以下の歩道で結ばれることも分かる。

(3)を示す。定理 2.1の証明と同じく

と置く。同じ証明のとおり、§D2.2 命題 1.5より$\lvert I\rvert=\deg_G(x_1)$、$\lvert J\rvert=\deg_G(x_n)$である。$I\cup J\subseteq\{2,\dots,n\}$であるから$\lvert I\cup J\rvert\le n-1$であり、§D2.2 定理 2.1を(2)の解答と同じく用いると

である。$x_1x_n\notin E$であるから$n\notin I$かつ$2\notin J$であり、$I\cap J\subseteq\{3,\dots,n-1\}$である。

$i\in I\cap J$に対し、頂点列

を考える。定理 2.1の証明の「閉路の構成」の段と同じく、$i\in I$と$i\in J$と$3\le i\le n$から、$C_i$は$G$の Hamilton 閉路である。$C_i$の辺集合$E(C_i)$は、Hamilton 道の辺$x_jx_{j+1}$（$1\le j\le n-1$、$j\ne i-1$）と、辺$x_{i-1}x_n$、$x_ix_1$からなる。$3\le i\le n-1$であるから$x_n\ne x_i$かつ$x_1\ne x_{i-1}$であり、辺$x_{i-1}x_n$と辺$x_ix_1$はどちらも辺$x_{i-1}x_i$と異なる。Hamilton 道の頂点は相異なるので、辺$x_{i-1}x_i$は$j\ne i-1$に対する辺$x_jx_{j+1}$とも異なる。ゆえに$x_{i-1}x_i\notin E(C_i)$である。一方、$i'\in I\cap J$、$i'\ne i$ならば、$i-1\ne i'-1$であるから$x_{i-1}x_i\in E(C_{i'})$である。したがって$I\cap J$の相異なる元は辺集合が異なる Hamilton 閉路を与え、その個数は$\lvert I\cap J\rvert\ge\deg_G(x_1)+\deg_G(x_n)-n+1$以上である。

後半を示す。$E_0$は$\{u,v\}$以外のすべての二元部分集合からなるので、$\deg_{G_0}(u)=\deg_{G_0}(v)=n-2$であり、$uv\notin E_0$である。$V\setminus\{u,v\}$の$n-2$個の元を任意の順に$x_2,\dots,x_{n-1}$と並べ、$x_1=u$、$x_n=v$と置く。$1\le i\le n-1$について$\{i,i+1\}\ne\{1,n\}$であるから$\{x_i,x_{i+1}\}\ne\{u,v\}$であり、$x_ix_{i+1}\in E_0$である。ゆえに$x_1,\dots,x_n$は$u$から$v$への$G_0$の Hamilton 道である。$n\ge4$であるから$\deg_{G_0}(u)+\deg_{G_0}(v)=2n-4\ge n$であり、前半の主張を適用することができる。下界の値は$(2n-4)-n+1=n-3$である。

次に、Hamilton 閉路を数える。$V$の相異なる元をすべて並べた列$y=(y_1,\dots,y_n)$の全体を$\mathcal X$とすると、§D2.2 命題 3.1を$k=n$として用いて$\lvert\mathcal X\rvert=n!$である。$y\in\mathcal X$に対し

と置き、$\mathcal Y=\{H(y):\ y\in\mathcal X\}$と置く。$V$上のグラフ$(V,E')$の Hamilton 閉路$x_1,\dots,x_n,x_1$の辺集合は$H(x)$であり、逆に$y\in\mathcal X$が$H(y)\subseteq E'$を満たせば$y_1,\dots,y_n,y_1$は$(V,E')$の Hamilton 閉路である。したがって、辺集合が互いに異なる$(V,E')$の Hamilton 閉路の個数は、$H\subseteq E'$を満たす$H\in\mathcal Y$の個数に等しい。

$\lvert\mathcal Y\rvert$を求める。$y\in\mathcal X$を固定して$H=H(y)$と置き、添字は$n$を法として読む（$y_{m+n}=y_m$）。$y_1,\dots,y_n$は相異なり$n\ge3$であるから、$y_m$を含む$H$の元は$\{y_{m-1},y_m\}$と$\{y_m,y_{m+1}\}$の二つだけであり、$y_{m-1}\ne y_{m+1}$である。すなわち、グラフ$(V,H)$で$y_m$に隣接する頂点は$y_{m-1}$と$y_{m+1}$のちょうど二つである。$1\le j\le n$と$\varepsilon\in\{1,-1\}$に対し

と置く。$z^{(j,\varepsilon)}$は$y$の項を巡回的にずらし、必要なら逆順にした列であるから$\mathcal X$に属し、連続する二項と末項・初項の対はちょうど$\{y_m,y_{m+1}\}$（$1\le m\le n$）であるので$H(z^{(j,\varepsilon)})=H$である。これら$2n$個の列は相異なる。実際、$j$が異なれば初項が異なり、$j$が等しく$\varepsilon$が異なれば第二項$y_{j+1}$と$y_{j-1}$が異なる。逆に、$z\in\mathcal X$が$H(z)=H$を満たすとし、$z_1=y_j$となる$j$を取る。$\{z_1,z_2\}\in H$であるから$z_2\in\{y_{j+1},y_{j-1}\}$であり、$z_2=y_{j+\varepsilon}$となる$\varepsilon\in\{1,-1\}$を取る。$1\le k\le n$について$z_k=y_{j+(k-1)\varepsilon}$であることを$k$についての帰納法で示す。$k=1,2$では成り立つ。$2\le k\le n-1$とし、$k$以下で成り立つとする。$\{z_k,z_{k+1}\}\in H$であるから、$z_{k+1}$は$(V,H)$で$z_k=y_{j+(k-1)\varepsilon}$に隣接し、$z_{k+1}\in\{y_{j+k\varepsilon},y_{j+(k-2)\varepsilon}\}$である。$z$の項は相異なるので$z_{k+1}\ne z_{k-1}=y_{j+(k-2)\varepsilon}$であり、$z_{k+1}=y_{j+k\varepsilon}$である。ゆえに$z=z^{(j,\varepsilon)}$である。以上より、写像$y\mapsto H(y)$による各$H\in\mathcal Y$の逆像はちょうど$2n$個の元をもつ。この写像は$\mathcal X$から$\mathcal Y$への全射であるから、§D2.2 命題 2.2により$n!=2n\lvert\mathcal Y\rvert$、すなわち$\lvert\mathcal Y\rvert=(n-1)!/2$である。

$\{u,v\}\in H$を満たす$H\in\mathcal Y$の全体を$\mathcal Y_{uv}$とし、$y_1=u$かつ$y_n=v$を満たす$y\in\mathcal X$の全体を$\mathcal X_{uv}$とする。$\mathcal X_{uv}$の元は$V\setminus\{u,v\}$の元を第$2$項から第$n-1$項に並べた列と一対一に対応するので、§D2.2 命題 3.1により$\lvert\mathcal X_{uv}\rvert=(n-2)!$である。$y\in\mathcal X_{uv}$ならば$\{y_n,y_1\}=\{u,v\}\in H(y)$であるから、写像$y\mapsto H(y)$は$\mathcal X_{uv}$を$\mathcal Y_{uv}$へ写す。この写像が全単射であることを示す。$H\in\mathcal Y_{uv}$とし、$H(y)=H$を満たす$y\in\mathcal X$と、$y_j=u$を満たす$j$を取る。前段により$H$の逆像は$z^{(j',\varepsilon)}$の$2n$個であり、そのうち初項が$u$であるものは$z^{(j,1)}$と$z^{(j,-1)}$の二つで、それぞれの末項は$y_{j-1}$と$y_{j+1}$である。$\{u,v\}\in H$であるから$v$は$(V,H)$で$u$に隣接し、相異なる二頂点$y_{j-1}$、$y_{j+1}$のちょうど一方に等しい。ゆえに$H$の逆像のうち$\mathcal X_{uv}$に属するものはちょうど一つである。したがって§D2.2 命題 1.5により$\lvert\mathcal Y_{uv}\rvert=\lvert\mathcal X_{uv}\rvert=(n-2)!$である。