Bondy–Chvátalの閉包定理

1：操作で加えた辺を順に $e_1,\dots,e_r$ とし、$G''$ の辺でないものがあるとして、その最初のものを $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 k$ である。$e_1,\dots,e_l$ と $G$ の辺は $G''$ の辺なので $H\subset G''$ であり、$\deg_{G''}(u)+\deg_{G''}(v)\ge k$ となる。$uv$ は $G''$ の辺でないので、これは $G''$ が $k$-閉であることに反する。
2：操作を 2 通りに行って得られるグラフ $G_1,G_2$ はどちらも $G$ を含む $k$-閉なグラフなので、1 により $G_1\subset G_2$ かつ $G_2\subset G_1$ である。$G$ を含む $k$-閉なグラフ $G''$ はどれも、1 により $\operatorname{cl}_k(G)$ を含む。
3：$\operatorname{cl}_k(G')$ は $G'$ を含むので $G$ を含み、$k$-閉である。1 による。
4：$\operatorname{cl}_k(G)$ は $k$-閉である。$k\le k'$ なら、隣接しない組の次数の和が $k$ 未満なので $k'$ 未満でもあり、$\operatorname{cl}_k(G)$ は $k'$-閉である。$G$ を含むので、1 による。$\square$

1：$\operatorname{cl}_k(G)$ を作るときに加えた辺を順に $e_1,\dots,e_r$ とし、$G_j:=G+\{e_1,\dots,e_j\}$（$G_0=G$、$G_r=\operatorname{cl}_k(G)$）とおく。$e_{j+1}$ の両端は $G_j$ で隣接せず、$G_j$ での次数の和が $k$ 以上なので、$k$-安定性により $G_{j+1}$ が $\mathcal{P}$ をみたせば $G_j$ もみたす。$j=r-1,\dots,0$ と順にたどればよい。
2：$G\subset\operatorname{cl}_k(G)$ なので、$G$ が $\mathcal{P}$ をみたせば $\operatorname{cl}_k(G)$ もみたす。逆は 1 である。
3：$\operatorname{cl}_k(G)$ で隣接しない相異なる 2 頂点 $x,y$ があるとすると、$x,y$ は $G$ でも隣接せず、$\deg_{\operatorname{cl}_k(G)}(x)+\deg_{\operatorname{cl}_k(G)}(y)\ge\deg_G(x)+\deg_G(y)\ge k$ となって $\operatorname{cl}_k(G)$ が $k$-閉であることに反する。よって $\operatorname{cl}_k(G)=K_n$ であり、後半は 1 による。$\square$

以下、$G$ で隣接しない相異なる 2 頂点 $u,v$ をとる。とくに $n\ge2$ である。
2：$\deg_G(u)+\deg_G(v)\ge n-1$ とし、$G+uv$ が Hamilton 路をもつとする。$G$ に新しい頂点 $w$ を加え、$w$ を $V$ のすべての頂点と結んだ $n+1$ 頂点のグラフを $G^*$ とする。$n\ge2$ なので $n+1\ge3$ である。$G$ が Hamilton 路 $v_1,\dots,v_n$ をもてば $w,v_1,\dots,v_n,w$ は $G^*$ の Hamilton 閉路であり、逆に $G^*$ の Hamilton 閉路から $w$ を除くと $G$ の Hamilton 路が残る。よって $G$ が Hamilton 路をもつことと $G^*$ が Hamilton 閉路をもつことは同値で、同じことが $G+uv$ と $(G+uv)^*=G^*+uv$ についても成り立つ。$u,v$ は $G^*$ で隣接せず、
$$ \deg_{G^*}(u)+\deg_{G^*}(v)=\deg_G(u)+\deg_G(v)+2\ge n+1=\lvert V(G^*)\rvert $$
である。$G^*+uv$ は Hamilton 閉路をもつので、1 を $n+1$ 頂点のグラフ $G^*$ に当てると $G^*$ も Hamilton 閉路をもち、$G$ は Hamilton 路をもつ。
3：$\deg_G(u)+\deg_G(v)\ge n+1$ とし、$G+uv$ が Hamilton 連結であるとする。相異なる 2 頂点 $x,y$ をとり、$G$ に新しい頂点 $w$ を加えて $w$ を $x,y$ の 2 頂点とだけ結んだグラフを $G_{xy}$ とする。$G$ に $x$ と $y$ を両端とする Hamilton 路があれば、それに $w$ をつないで $G_{xy}$ の Hamilton 閉路が得られる。逆に $G_{xy}$ の Hamilton 閉路は $w$ を通り、$w$ の隣接頂点は $x,y$ だけなので、閉路の中で $x,w,y$ と続く。$w$ を除くと、$x$ と $y$ を両端とする $G$ の Hamilton 路が残る。$w\ne u,v$ なので $(G+uv)_{xy}=G_{xy}+uv$ であり、$u,v$ は $G_{xy}$ で隣接せず、
$$ \deg_{G_{xy}}(u)+\deg_{G_{xy}}(v)\ge\deg_G(u)+\deg_G(v)\ge n+1=\lvert V(G_{xy})\rvert $$
である。$G+uv$ は Hamilton 連結なので $G_{xy}+uv$ は Hamilton 閉路をもち、1 により $G_{xy}$ も Hamilton 閉路をもつ。よって $G$ に $x$ と $y$ を両端とする Hamilton 路がある。$x,y$ は任意なので $G$ は Hamilton 連結である。$\square$

$G$ で隣接しない相異なる 2 頂点 $u,v$ をとる。
4：$\deg_G(u)+\deg_G(v)\ge n+q-2$ とし、$G+uv$ は $q$-連結、$G$ は $q$-連結でないとして矛盾を導く。$G+uv$ が $q$-連結なので $n>q$ である。よって、$\lvert X\rvert< q$ で $G-X$ が連結でない $X\subset V$ がある。$(G+uv)-X$ は連結である。$u\in X$ か $v\in X$ なら $G-X=(G+uv)-X$ となって矛盾するので、$u,v\notin X$ であり、$G-X$ は連結なグラフ $(G+uv)-X$ から辺 $uv$ を除いたものである。連結なグラフから辺を 1 本除くと連結成分は高々 2 つになり、2 つになるときはその辺の両端が別の成分に入る。よって $G-X$ はちょうど 2 つの成分 $C_u\ni u$、$C_v\ni v$ をもつ。$u$ の隣接頂点は $C_u\setminus\{u\}$ か $X$ にあり、$v$ についても同様なので、
$$ \deg_G(u)+\deg_G(v)\le\bigl(\lvert C_u\rvert-1+\lvert X\rvert\bigr)+\bigl(\lvert C_v\rvert-1+\lvert X\rvert\bigr)=n+\lvert X\rvert-2\le n+q-3 $$
である（$\lvert C_u\rvert+\lvert C_v\rvert=n-\lvert X\rvert$）。これは仮定に反する。
5：$\deg_G(u)+\deg_G(v)\ge2s-1$ とし、$G+uv$ は大きさ $s$ のマッチング $M$ をもち、$G$ はもたないとして矛盾を導く。$M$ は辺 $uv$ を含む（含まなければ $G$ のマッチングである）。$M':=M\setminus\{uv\}$ は $s-1$ 本の辺からなり、その端点の集合 $W$ は $2s-2$ 個の頂点からなり $u,v$ を含まない。
$u$ が $W\cup\{v\}$ の外の頂点 $x$ と $G$ で隣接すれば、$M'\cup\{ux\}$ は $G$ の大きさ $s$ のマッチングになる。$uv$ は $G$ の辺でないので、$u$ の隣接頂点はすべて $W$ にある。$v$ についても同様である。
$M'$ の辺 $ab$ を 1 本とる。$ua$ と $vb$ がともに $G$ の辺なら、$(M'\setminus\{ab\})\cup\{ua,vb\}$ は $G$ の大きさ $s$ のマッチングになる。$ub$ と $va$ についても同様である。よって $\{u,v\}$ と $\{a,b\}$ を結ぶ 4 本の可能な辺のうち、組 $\{ua,vb\}$ の両方、組 $\{ub,va\}$ の両方が同時に辺であることはなく、辺は高々 $2$ 本である。$W$ は $M'$ の $s-1$ 本の辺の端点に分かれるので、
$$ \deg_G(u)+\deg_G(v)\le2(s-1)=2s-2 $$
となって仮定に反する。$n$ が偶数で $s=n/2$ のとき、大きさ $s$ のマッチングは完全マッチングである。$\square$

thm-bc-main の 3 と thm-bc-stable により、$K_n$ がそれぞれの性質をみたすことを確かめればよい。$K_n$ の頂点を任意の順に並べたものは Hamilton 路であり、両端を $x,y$ に選べるので $K_n$ は Hamilton 連結である。$n\ge q+1$ のとき $K_n$ から $q$ 個未満の頂点を除いても 1 頂点以上の完全グラフが残るので、$K_n$ は $q$-連結である。$\square$

prf-bc-stable-path の $G^*$（新しい頂点 $w$ を $V$ のすべての頂点と結んだグラフ）を考える。$G^*$ の頂点数は $n+1\ge3$ で、$V$ の頂点の次数は $1$ 増え、$w$ の次数は $n$ である。$d_i+1\le n$ なので、$G^*$ の次数を小さい順に並べた列は $d^*_i=d_i+1$（$1\le i\le n$）、$d^*_{n+1}=n$ である。$1\le m<(n+1)/2$ とし、$d^*_m\le m$、すなわち $d_m< m$ とする。仮定により $d_{n-m+1}\ge n-m$ であり、$n-m+1\le n$ なので $d^*_{n+1-m}=d_{n-m+1}+1\ge(n+1)-m$ である。よって $G^*$ は Chvátal の定理の仮定をみたし、Hamilton 閉路をもつ。prf-bc-stable-path の 2 で見たとおり、$G$ は Hamilton 路をもつ。$\square$

1：Oreの定理(Hamilton閉路) の例「反例：補題の和を $n-1$ にすると成り立たない」で確かめた（次数の和は $2m=n-1$）。
2：次数の和は $2m=n-2$ である。二部グラフの道は 2 つの部の頂点を交互に通るので、Hamilton 路があれば部の大きさの差は $1$ 以下であり、$K_{m,m+2}$ は Hamilton 路をもたない。大きい部を $u=b_0,v=b_1,b_2,\dots,b_{m+1}$、小さい部を $a_1,\dots,a_m$ とすると、$b_0,b_1,a_1,b_2,a_2,\dots,b_m,a_m,b_{m+1}$ は $K_{m,m+2}+uv$ の Hamilton 路である。
3：残りの頂点を $a,b$ とする。$c,d$ の次数はどちらも $2$ で和は $4=n$ である。$G+cd=K_4$ は Hamilton 連結である。$G$ で $a$ と $b$ を両端とする Hamilton 路は $a,x,y,b$（$\{x,y\}=\{c,d\}$）の形で、$xy=cd$ が辺でないのでない。
4：$\deg(u)+\deg(v)=(a-1+q-1)+(b-1+q-1)=n+q-3$ である。$G-S$ は $A$ と $B$ に分かれて連結でなく、$\lvert S\rvert< q$ なので $G$ は $q$-連結でない。$G+uv$ については、$n\ge q+1$ であり、$\lvert X\rvert< q$ のとき、$S\not\subset X$ なら残った $S$ の頂点がほかのすべての残った頂点と隣接するので $(G+uv)-X$ は連結で、$S\subset X$ なら $X=S$ で、$(G+uv)-S$ は $A$ 上と $B$ 上の完全グラフを辺 $uv$ で結んだもので連結である。
5：次数の和は $2(s-1)=2s-2$ である。$G$ のどの辺もある $a_i$ を端点にもつので、マッチングは高々 $s-1$ 本の辺からなる。$G+uv$ では $\{uv,a_1b_1,\dots,a_{s-1}b_{s-1}\}$ が大きさ $s$ のマッチングである。$\square$