7-2 Hamiltonグラフ

Hamilton cycle $C$ は全頂点を含むので、$C$ の辺だけでも全頂点が連結され、$G$ は連結です。
任意の頂点 $v$ を取ります。cycle $C$ から $v$ とその接続二辺を除くと、残りの全頂点を含むpathになります。従って $G-v$ はそのpathを部分グラフとして含み、連結です。よって $v$ はcut vertexではありません。
またHamilton cycle上で各頂点には直前と直後の相異なる二頂点が隣接するため、次数は2以上です。□

$G$ のHamilton cycleを $C$ とします。$S$ の頂点をcycleから削除します。cycle上で削除された頂点が連続している場合もありますが、残る辺は高々 $|S|$ 本の互いに頂点素なpathへ分かれます。
詳しくは、$C-S$ の各非空path成分の直前には、cycleの向きに見て $S$ の頂点があります。異なるpath成分には異なる直前頂点が対応するため、$C-S$ の成分数は高々 $|S|$ です。
$G-S$ は $C-S$ に辺を追加したグラフです。辺を追加して連結成分数が増えることはないので
$$ c(G-S)\le c(C-S)\le |S|. $$
□

二部グラフの各辺は一方の部から他方の部へ渡るので、pathまたはcycle上の頂点は $X,Y,X,Y,\ldots$ と交互に並びます。cycleでは開始部へ戻るため両部の出現回数が等しいです。Hamilton cycleは全頂点を含むので $|X|=|Y|$ です。
pathでは両端が異なる部なら出現回数は等しく、同じ部ならその部が一つ多くなります。従って差の絶対値は高々1です。□

必要性は前命題から従います。十分性を示します。二つの部を
$$ X=\{x_1,\ldots,x_m\},\qquad Y=\{y_1,\ldots,y_n\} $$
とします。
$m=n\ge2$ なら
$$ x_1,y_1,x_2,y_2,\ldots,x_n,y_n,x_1 $$
はHamilton cycleです。$m=n$ なら最後の $x_1$ を除いた列がHamilton pathです。$m=n+1$ なら
$$ x_1,y_1,x_2,y_2,\ldots,x_n,y_n,x_{n+1} $$
がHamilton pathで、$n=m+1$ も部を交換すれば同様です。□

$G$ が非連結と仮定し、最小の連結成分の頂点数を $r$ とします。成分が二つ以上あるので $r\le n/2$ です。その成分内の頂点は成分外へ隣接できず、次数は高々 $r-1< n/2$ です。これは最小次数条件に反します。□

$G$ の最長pathを
$$ P=(v_1,v_2,\ldots,v_k) $$
とします。最長性により、端点 $v_1,v_k$ のすべての隣接頂点は $P$ 上にあります。もし外部の頂点へ隣接すれば、その頂点を端へ付けてより長いpathを作れるからです。
添字集合 $\{1,2,\ldots,k-1\}$ の二つの部分集合
$$ A=\{i\mid v_1v_{i+1}\in E(G)\},\qquad B=\{i\mid v_iv_k\in E(G)\} $$
を考えます。$v_1$ の隣接頂点はすべて $v_2,\ldots,v_k$ にあるので $|A|=\deg(v_1)$、同様に $|B|=\deg(v_k)$ です。従って
$$ |A|+|B|=\deg(v_1)+\deg(v_k)\ge n. $$
一方、$A,B$ はともに $k-1$ 個の添字からなる集合の部分集合で、$k\le n$ です。もし $A\cap B=\varnothing$ なら
$$ |A|+|B|\le k-1\le n-1 $$
となり矛盾します。従ってある $i\in A\cap B$ があります。
この $i$ に対し
$$ v_1,v_2,\ldots,v_i,v_k,v_{k-1},\ldots,v_{i+1},v_1 $$
はcycleです。最初の区間と逆向きの区間では $P$ の辺を使い、つなぎ目では $v_iv_k$ と $v_{i+1}v_1$ を使っています。これは $P$ の全 $k$ 頂点を含みます。
もし $k< n$ なら、このcycleの外に頂点があります。補題 [26-lem-dirac-connected] により $G$ は連結なので、cycle外の頂点からcycleへ至るpathを取り、cycleへ初めて入る辺 $xy$ を選べます。ここで $x$ はcycle外、$y$ はcycle上です。cycleから $y$ に接続する二辺の一方を外し、$x,y$ と進んでからcycleを一周すれば、cycleの $k$ 頂点と $x$ をすべて含むpathができます。これは $P$ より長く、最長性に反します。
従って $k=n$ であり、構成したcycleは全頂点を含むHamilton cycleです。□

$G+uv$ のHamilton cycleが追加辺 $uv$ を使わないなら、そのcycleは既に $G$ にあります。追加辺を使う場合、$uv$ を除くと $G$ 内のHamilton path
$$ u=x_1,x_2,\ldots,x_n=v $$
が得られます。
$\{1,\ldots,n-1\}$ の部分集合
$$ A=\{i\mid ux_{i+1}\in E(G)\},\qquad B=\{i\mid x_iv\in E(G)\} $$
を考えます。$u,v$ は非隣接なので、$u$ の全隣接頂点は $x_2,\ldots,x_{n-1}$ に、$v$ の全隣接頂点は $x_2,\ldots,x_{n-1}$ にあり、それぞれ $|A|=\deg_G(u)$、$|B|=\deg_G(v)$ です。
次数和が $n$ 以上である一方、添字は $n-1$ 個しかないため、$A\cap B$ は空ではありません。$i\in A\cap B$ を取れば
$$ u=x_1,x_2,\ldots,x_i,v=x_n,x_{n-1},\ldots,x_{i+1},u $$
は $G$ のHamilton cycleです。□

$G$ に欠けている辺を一つずつ加え、完全グラフ $K_n$ にします。辺を加えると頂点次数は減らないので、各段階でまだ非隣接な二頂点の次数和条件は保たれます。
$K_n$ はHamilton graphです。最後に加えた辺から逆順に取り除きます。各辺を加える直前のグラフでは、その両端の次数和が $n$ 以上だったので、補題 [26-lem-ore-edge-addition] により、その辺を取り除いてもHamilton cycleの存在は保たれます。すべての追加辺を取り除くと元の $G$ がHamilton graphだと分かります。□

$|S|$ に関する帰納法で、$H(S,v)$ の意味が定義文のpathの存在と一致することを示します。一頂点の場合は初期値どおりです。
$S$ をちょうど一度ずつ使って $v$ で終わるpathがあるなら、$v$ の直前の頂点を $u$ とすると $uv\in E(G)$ で、最後の $v$ を除いた部分は $S\setminus\{v\}$ をちょうど一度ずつ使って $u$ で終わるpathです。帰納法により右辺の対応する項がtrueです。
逆に右辺のある項 $H(S\setminus\{v\},u)$ がtrueなら、帰納法で得られるpathの末尾へ辺 $uv$ と未使用頂点 $v$ を加えれば、$S$ をちょうど一度ずつ使って $v$ で終わるpathになります。従って漸化式は正しいです。
最後に $S=V(G)$ とし、そのpathの終点 $v$ が開始点1に隣接すれば、辺 $v1$ を加えてHamilton cycleになります。逆に1を開始点とするHamilton cycleから最後の辺を除けば、そのような状態が得られます。□

$n$ に関する帰納法で示します。$n=2$ では
$$ 00,01,11,10,00 $$
がHamilton cycleです。
$Q_n$ のHamilton cycleから開始頂点を重ねずに切った頂点列を
$$ g_1,g_2,\ldots,g_{2^n} $$
とし、連続する $g_i,g_{i+1}$ および $g_{2^n},g_1$ が一bitだけ異なるとします。
$Q_{n+1}$ で次の列を考えます。
$$ 0g_1,0g_2,\ldots,0g_{2^n}, 1g_{2^n},1g_{2^n-1},\ldots,1g_1,0g_1. $$
最初の半分と後半の逆順部分では、帰納法により末尾 $n$ bitの一箇所だけが変わります。中央の $0g_{2^n}$ と $1g_{2^n}$、最後の $1g_1$ と $0g_1$ は先頭bitだけが異なります。
先頭bitが0の全頂点と1の全頂点をそれぞれ一度ずつ含むので、これは $Q_{n+1}$ の全 $2^{n+1}$ 頂点を一度ずつ訪れるcycleです。帰納法により全 $n\ge2$ で成立します。□

外周を順に $v_1,v_2,\ldots,v_{n-1},v_1$、中心を $c$ とします。外周の辺 $v_{n-1}v_1$ の代わりに中心を通れば
$$ c,v_1,v_2,\ldots,v_{n-1},c $$
となります。中心と全外周頂点を一度ずつ含むのでHamilton cycleです。$n=4$ でも同じ構成が使えます。□

共有頂点の次数は4、他の頂点の次数は2です。グラフは連結で全次数が偶数なので、Euler定理によりEuler circuitをもちます。
共有頂点を除くと、二つのcycleの残りが別々の連結成分になります。従って共有頂点はcut vertexです。命題 [26-prop-hamilton-two-connected] によりHamilton graphはcut vertexをもたないので、このグラフにHamilton cycleはありません。辺を尽くせても頂点を一度ずつ尽くせるとは限らない例です。□

大きさ2の部を $S$ とします。$S$ を削除すると、大きさ4の他方の部の各頂点は孤立し、
$$ c(K_{2,4}-S)=4>2=|S| $$
です。Hamilton graphが満たすべき成分数条件に反するので、Hamilton cycleはありません。□

$n=10$ で最小次数は5以上、すなわち
$$ \delta(G)\ge5=\frac{10}{2} $$
です。Diracの定理の仮定を満たすため、連結性を別に確認しなくてもHamilton cycleが存在します。実際、連結性はDirac定理の証明中の補題から自動的に従います。
反例として $K_{4,6}$ を取れます。小さい部の頂点次数は6、大きい部の頂点次数は4なので最小次数は4です。しかし二部の大きさが異なるためHamilton cycleをもちません。□

$G$ は6頂点です。$v$ の次数は3なので
$$ \delta(G)=3=\frac62 $$
となり、実はこのままではDirac条件を満たします。従って問題文の主張はこの例では成立しません。この計算は、候補例を定理へ当てる前に次数を確認すべきことを示します。
正しい例へ修正します。$K_6$ から同じ頂点 $v$ に接続する三辺 $va,vb,vc$ を削除します。このとき $deg(v)=2<3$ なのでDirac条件を満たしません。非隣接対は $(v,a),(v,b),(v,c)$ だけで、$a,b,c$ の次数は4です。従って各非隣接対の次数和は
$$ 2+4=6=n $$
となり、Ore条件を満たします。ゆえに修正後のグラフはOreの定理によりHamilton graphです。□

$Q_3$ の列
$$ 000,001,011,010,110,111,101,100 $$
の前に0を付け、その逆順の前に1を付けます。得られる巡回列は
$$ \begin{aligned} &0000,0001,0011,0010,0110,0111,0101,0100,\\ &1100,1101,1111,1110,1010,1011,1001,1000,0000. \end{aligned} $$
各半分の内部では末尾3 bitの一箇所だけが変わります。中央の $0100,1100$ と最後の $1000,0000$ は先頭bitだけが変わります。先頭0の8列と先頭1の8列がそれぞれ末尾三bitの全状態を一度ずつ含むため、16頂点は重複なく尽くされています。□