Oreの定理(Hamilton閉路)

$G$ が Hamilton 閉路をもてば、$G+uv$ も同じ閉路をもつ。逆に、$G+uv$ が Hamilton 閉路 $C$ をもち、$G$ はもたないとする。$C$ は辺 $uv$ を通る（通らなければ $C$ は $G$ の Hamilton 閉路である）。$C$ から辺 $uv$ を除くと、$G$ の Hamilton 路 $u=v_1,v_2,\dots,v_n=v$ が得られる（$C$ は長さ $n\ge3$ の閉路なので $n\ge3$ である）。
$$ S:=\{\,i\mid 1\le i\le n-1,\ uv_{i+1}\in E\,\},\qquad T:=\{\,i\mid 1\le i\le n-1,\ v_iv\in E\,\} $$
とおく。$u$ 以外の頂点は $v_2,\dots,v_n$、$v$ 以外の頂点は $v_1,\dots,v_{n-1}$ なので、$\lvert S\rvert=\deg_G(u)$、$\lvert T\rvert=\deg_G(v)$ である。$S\cap T$ が元 $i$ をもてば、$uv\notin E$ より $2\le i\le n-2$ であり、
$$ v_1,\ \dots,\ v_i,\ v_n,\ v_{n-1},\ \dots,\ v_{i+1},\ v_1 $$
は辺 $v_iv_n$ と $v_{i+1}v_1$ を使う $G$ の Hamilton 閉路になって仮定に反する。よって $S\cap T=\emptyset$ であり、$S\cup T\subset\{1,\dots,n-1\}$ から $\deg_G(u)+\deg_G(v)=\lvert S\cup T\rvert\le n-1$ となって、$\deg_G(u)+\deg_G(v)\ge n$ に反する。$\square$

$G_1$ を得るときに加えた辺を順に $e_1,\dots,e_r$、$G_2$ を得るときに加えた辺を順に $f_1,\dots,f_s$ とする。どの $e_j$ も $G_2$ の辺であることを示す。そうでないとし、$G_2$ の辺でない最初の $e_j$ を $e_{l+1}=uv$ とする。$H:=G+\{e_1,\dots,e_l\}$（$G$ にこれらの辺を加えたグラフ）とおくと、$e_{l+1}$ を加えた時点の条件から $u,v$ は $H$ で隣接せず、$\deg_H(u)+\deg_H(v)\ge n$ である。$e_1,\dots,e_l$ は $G_2$ の辺なので $H$ は $G_2$ に含まれ、$\deg_{G_2}(u)+\deg_{G_2}(v)\ge\deg_H(u)+\deg_H(v)\ge n$ である。$uv$ は $G_2$ の辺でないから、$G_2$ にはまだ結べる組 $u,v$ が残っていることになり、$G_2$ が操作の終わりであることに反する。よって $G_1$ の辺はすべて $G_2$ の辺であり、同様に $G_2$ の辺はすべて $G_1$ の辺である。どちらも頂点集合は $V$ なので $G_1=G_2$ である。$\square$

1：閉包を作るときに加えた辺を順に $e_1,\dots,e_r$ とし、$G_j:=G+\{e_1,\dots,e_j\}$（$G_0=G$、$G_r=\operatorname{cl}(G)$）とおく。$e_{j+1}$ の両端は $G_j$ で隣接せず、$G_j$ での次数の和が $n$ 以上なので、lem-ore-bc により $G_j$ と $G_{j+1}$ の Hamilton 閉路の有無は一致する。$j=0,\dots,r-1$ についてつなげればよい。
2：$n\ge3$ なら $K_n$ の頂点を任意の順に並べた $v_1,\dots,v_n,v_1$ は Hamilton 閉路である。1 により $G$ も Hamilton 閉路をもつ。$\square$

$\operatorname{cl}(G)$ で隣接しない相異なる 2 頂点 $x,y$ があるとする。閉包は $G$ に辺を加えたものなので、$x,y$ は $G$ でも隣接せず、Ore の条件から
$$ \deg_{\operatorname{cl}(G)}(x)+\deg_{\operatorname{cl}(G)}(y)\ge\deg_G(x)+\deg_G(y)\ge n $$
である。これは $\operatorname{cl}(G)$ にまだ結べる組が残っていることを意味し、閉包の定義に反する。よって $\operatorname{cl}(G)=K_n$ であり、thm-ore-closure の 2 により $G$ は Hamilton 閉路をもつ。$\square$

どの 2 頂点 $u,v$ についても $\deg(u)+\deg(v)\ge\frac n2+\frac n2=n$ なので、thm-ore-main の仮定がみたされる。$\square$

隣接しない相異なる 2 頂点 $u,v$ をとる（なければ $G=K_n$ で、Hamilton 閉路をもつ）。$G$ の辺は、$u$ にも $v$ にも接続しないものと、$u$ か $v$ に接続するものに分かれる。前者は残りの $n-2$ 頂点の間の辺なので $\binom{n-2}2$ 本以下であり、後者は $uv$ が辺でないので $\deg(u)+\deg(v)$ 本である。よって
$$ \binom{n-1}2+2\le\binom{n-2}2+\deg(u)+\deg(v) $$
であり、$\binom{n-1}2-\binom{n-2}2=n-2$ から $\deg(u)+\deg(v)\ge n$ を得る。$G$ は Ore の条件をみたすので、thm-ore-main により Hamilton 閉路をもつ。$\square$

$H:=\operatorname{cl}(G)$ とおき、$H$ での次数を $d'(x)$ と書く。$H$ の次数は $G$ の次数以上である。
まず、$G$ に次数 $0$ の頂点 $x$ はない。あれば $d_1=0\le1$ であり、ほかの頂点はどれも $x$ と隣接しないので次数が $n-2$ 以下、とくに $d_{n-1}\le n-2< n-1$ となって、$m=1$（$n\ge3$ なので $1< n/2$）について仮定に反する。
$H\ne K_n$ として矛盾を導く。$H$ で隣接しない相異なる 2 頂点の組のうち、$H$ での次数の和が最大のものを 1 つとり、$d'(u)\le d'(v)$ となるように名前を付ける。$H$ は閉包なので $d'(u)+d'(v)\le n-1$ である。$m:=d'(u)$ とおくと、$m\ge\deg_G(u)\ge1$、$2m\le d'(u)+d'(v)\le n-1$ なので $1\le m< n/2$ である。
（次数の小さい頂点）$v$ と隣接しない $v$ 以外の頂点の集合を $X$ とする。$u\in X$ であり、$\lvert X\rvert=n-1-d'(v)\ge n-1-(n-1-m)=m$ である。$w\in X$ なら $w,v$ は $H$ で隣接しない組なので、和の最大性から $d'(w)+d'(v)\le d'(u)+d'(v)$、すなわち $d'(w)\le m$ である。
（次数の大きくない頂点）$u$ と隣接しない $u$ 以外の頂点の集合を $Y$ とする。$\lvert Y\rvert=n-1-m$ であり、$w\in Y$ なら同様に $d'(w)\le d'(v)\le n-1-m$ である。$u$ 自身も $d'(u)=m\le d'(v)\le n-1-m$ をみたす。$u\notin Y$ なので、$Y\cup\{u\}$ は $d'$ が $n-1-m$ 以下の $n-m$ 個の頂点からなる。
$G$ の次数は $H$ の次数以下なので、$G$ には次数 $m$ 以下の頂点が $m$ 個以上、次数 $n-1-m$ 以下の頂点が $n-m$ 個以上ある。次数を小さい順に並べると $d_m\le m$、$d_{n-m}\le n-1-m< n-m$ となり、仮定に反する。よって $H=K_n$ であり、thm-ore-closure の 2 により $G$ は Hamilton 閉路をもつ。$\square$

頂点を次数の小さい順に $x_1,\dots,x_n$ と並べ、$\deg(x_i)=d_i$ とする。ある $1\le m< n/2$ で $d_m\le m$ かつ $d_{n-m}\le n-m-1$ であるとして矛盾を導く。$i\le m$ とする。$1\le j\le n-m$、$j\ne i$ について $x_i$ と $x_j$ が隣接しなければ、$\deg(x_i)+\deg(x_j)\le m+(n-m-1)=n-1$ となって Ore の条件に反する。よって $x_i$ は $x_1,\dots,x_{n-m}$ のうち自分以外の $n-m-1$ 個とすべて隣接し、$n-m-1\le\deg(x_i)\le m$ である。$2m< n$ とあわせて $n=2m+1$ であり、$x_i$ の隣接頂点はちょうど $x_1,\dots,x_{m+1}$ のうち自分以外のものである。すると $x_n$（$n=2m+1>m+1$）は $x_1,\dots,x_m$ のどれとも隣接しないので $\deg(x_n)\le n-1-m=m$ であり、$\deg(x_1)+\deg(x_n)\le2m=n-1$ となって Ore の条件に反する。$\square$

1：$W_{m,n}$ から $B$ を除くと、$A$ の $m$ 個の孤立点と、$R$（$n-2m\ge1$ 個の頂点、完全グラフ）が残り、連結成分は $m+1$ 個である。Hamilton 閉路 $C$ から $B$ の $m$ 個の頂点を除くと、閉路は $m$ 個以下の道に切れるので、残りの頂点は高々 $m$ 個の連結成分に入る（Hamilton閉路 の命題「頂点を除いたときの連結成分の個数」）。よって Hamilton 閉路はない。
2：$A$ の頂点は $B$ とだけ隣接して次数 $m$、$R$ の頂点は $R$ の残りと $B$ に隣接して次数 $(n-2m-1)+m=n-m-1$、$B$ の頂点はほかのすべての頂点に隣接して次数 $n-1$ である。$2m\le n-1$ より $m\le n-m-1$ なので、小さい順に並べると主張の列になる。
3：$G$ は Hamilton 閉路をもたないので、thm-ore-chvatal の対偶により、ある $1\le m< n/2$ で $d_m\le m$ かつ $d_{n-m}\le n-m-1$ である。$i\le m$ なら $d_i\le d_m\le m$、$m< i\le n-m$ なら $d_i\le d_{n-m}\le n-m-1$、どの $i$ でも $d_i\le n-1$ である。$\square$