道・閉路・木：Euler 回路と Hamilton 閉路

0. この記事の要点

地図の上で、すべての道をちょうど 1 回ずつ通って出発点に戻れるか、あるいはすべての町をちょうど 1 回ずつ訪ねて戻れるか、という問いを考えます。町を点、道を線で表した図がグラフです。この記事では、グラフを調べるための基本的な言葉を整え、前者は線の集まり方を見るだけで判定できること、後者はそれほど簡単ではないものの、十分な条件なら示せることを順に証明します。

• 次数の和は辺数の 2 倍です（握手補題、補題 2.2）。これだけで「奇数次の頂点は偶数個」が出て、Euler 小道の端点の数え方を決めます。
• 最長の道を取り、その端点の近傍（その頂点と辺で結ばれた頂点の集まり）を調べるという論法を 1 回ていねいに書きます（命題 3.1）。端点の隣接点はすべて道の上にある、という一言が、長い閉路の存在、Dirac の定理、Ore の定理の証明の共通の出発点です。
• グラフが二部グラフであることと、奇数長の閉路を含まないことは同値です（定理 3.3）。
• 木は「連結で閉路がない」「2 頂点を結ぶ道がただ 1 本」「連結で辺が $n-1$ 本」など 6 通りに特徴づけられ（定理 4.4）、連結グラフは必ず全域木（すべての頂点を含む木）をもちます。
• 連結グラフが Euler 回路をもつのは、全頂点の次数が偶数のとき、そのときに限ります（定理 5.3）。局所的な条件だけで判定できます。
• Hamilton 閉路にはそのような判定条件が知られていません。十分条件として Dirac の定理（$\delta\ge n/2$。$\delta$ は各頂点の次数のうち最小のもの、$n$ は頂点の数）、Ore の定理、Bondy–Chvátal の閉包定理、Chvátal の次数列条件を、必要条件として $c(G-S)\le|S|$ を証明します。
• 整数の列がグラフの次数列になるかどうかは、Havel–Hakimi の定理（定理 7.2）で機械的に判定できます。

この記事で使う事前知識

• グラフ: 頂点の集まりと、頂点どうしを結ぶ辺の集まりの組。→ グラフ
• 同値関係: 反射・対称・推移の 3 つを満たす関係で、集合を同じ仲間ごとに分けるもの。→ 同値関係
• 非交和: 共通部分のない集合どうしの和。→ 非交和
• 整列性: 空でない非負整数の集合には最小の元がある、という性質。→ 整列性
• 対偶: 「A ならば B」に対する「B でないならば A でない」。もとの主張と同値です。→ 対偶

1. 動機

18 世紀の Königsberg には、川の中州と両岸を結ぶ 7 本の橋がありました。「すべての橋をちょうど 1 回ずつ渡って出発点に戻れるか」という問いに、Euler は 1736 年に「できない」と答えました。理由は、陸地を点、橋を線と見たとき、どの点にも奇数本の線が集まっているからです。歩いて通過するたびに線を 2 本ずつ使うので、戻ってくる散歩道があるなら、どの点に集まる線も偶数本でなければなりません。

Königsberg の橋。4 つの陸地を頂点、7 本の橋を辺とする多重グラフ。次数は 5, 3, 3, 3 で、すべて奇数

この答えの注目すべき点は、条件が各頂点のまわりだけを見れば確かめられることです。ところが、問いを「すべての頂点をちょうど 1 回ずつ通って戻れるか」（Hamilton 閉路）に変えると、事情が一変します。同じように局所的に確かめられる必要十分条件は知られておらず、判定問題は NP 完全（計算量の理論で、とくに難しい問題のクラス）です（P 対 NP 問題 を参照してください）。それでも「どの頂点も十分多くの頂点と隣接していれば Hamilton 閉路がある」という型の定理は証明できます。

この章は、グラフ理論のテーマ全体で使う語彙を定め、この 2 つの問いに答えます。グラフの定義と森の辺数（グラフと行列式 の 定義 2.1［グラフと行列式］ と 補題 2.2［グラフと行列式］）は既知とします。探索のアルゴリズムは グラフアルゴリズム にありますが、この章の証明はそれに依存しません。

2. 準備：次数・歩道・連結性

このテーマでは、断らない限りグラフは有限・単純・無向とします。すなわち 定義 2.1［グラフと行列式］ のグラフのうち多重辺のないものを考え、辺を端点の 2 元集合 $\{u,v\}$ と同一視して $uv$ と書きます。頂点集合を $V(G)$、辺集合を $E(G)$、$n=|V(G)|$、$m=|E(G)|$ とします。多重辺を許す場合（§5 の Euler 回路）はその場で断ります。

定義 2.1（隣接・次数）↗

$uv\in E(G)$ のとき $u$ と $v$ は隣接するといい、$v$ と辺 $uv$ は接続するという。頂点 $v$ の近傍を $N(v)=\{u\in V(G): uv\in E(G)\}$、次数を $d(v)=|N(v)|$（多重グラフでは $v$ に接続する辺の本数）と定める。最小次数を $\delta(G)=\min_v d(v)$、最大次数を $\Delta(G)=\max_v d(v)$ と書く。すべての頂点の次数が $k$ のグラフを $k$-正則という。

補題 2.2（握手補題）✓

多重辺を許すグラフ $G$ について

$$\sum_{v\in V(G)} d(v)=2m$$

が成り立つ。とくに、次数が奇数の頂点の個数は偶数である。

証明（補題 2.2）

頂点と辺の組 $(v,e)$ で $v$ が $e$ の端点であるものの集合を $I$ とし、$|I|$ を 2 通りに数えます。頂点ごとに数えると、$v$ を第 1 成分とする組は $d(v)$ 個なので $|I|=\sum_v d(v)$ です。辺ごとに数えると、各辺は相異なる 2 つの端点をもつ（自己ループはない）ので $|I|=2m$ です。

後半を示します。和 $\sum_v d(v)=2m$ は偶数です。偶数次の頂点の寄与は偶数なので、奇数次の頂点についての和 $\sum_{d(v)\text{ 奇}}d(v)$ も偶数です。奇数を $k$ 個足した和の偶奇は $k$ の偶奇と一致するので、$k$ は偶数です。

∎

定義 2.3（歩道・小道・道・閉路）↗

頂点の列 $W=v_0v_1\cdots v_k$ で、各 $i$ について $v_{i-1}v_i\in E(G)$ であるものを $v_0$ から $v_k$ への歩道といい、$k$ をその長さという（多重グラフでは使う辺 $e_i$ も指定する）。辺を重複して使わない歩道を小道、頂点を重複して通らない歩道を道という。$v_0=v_k$ である歩道を閉じているという。長さ $k\ge3$ の閉じた歩道で、$v_0,\dots,v_{k-1}$ が相異なるものを長さ $k$ の閉路という（定義 2.1［グラフと行列式］ の閉路と同じもの）。道・閉路は、それが使う頂点と辺からなるグラフとも見なす。

道 $P=v_0\cdots v_k$ と $0\le i\le j\le k$ に対し、部分列 $v_i\cdots v_j$ を $v_iPv_j$ と書く。

定義 2.4（部分グラフ・補グラフ・特別なグラフ）↗

$V(H)\subseteq V(G)$ かつ $E(H)\subseteq E(G)$ であるグラフ $H$ を $G$ の部分グラフといい、$V(H)=V(G)$ のとき全域部分グラフという。$S\subseteq V(G)$ に対し、頂点集合が $S$ で、両端が $S$ に入る $G$ の辺すべてを辺とするグラフ $G[S]$ を誘導部分グラフという。$G-S=G[V(G)\setminus S]$、$G-e$（辺 $e$ だけを除く）、$G+uv$（辺 $uv$ を足す）と書く。補グラフ $\overline G$ は、頂点集合が同じで、$uv\in E(\overline G)\iff uv\notin E(G)$（$u\ne v$）で定める。

• 完全グラフ $K_n$: $n$ 頂点のどの 2 つも隣接する。
• 二部グラフ: $V(G)=A\sqcup B$ と分割でき、どの辺も $A$ の頂点と $B$ の頂点を結ぶ。$(A,B)$ を二部分割という。
• 完全二部グラフ $K_{m,n}$: $|A|=m$、$|B|=n$ で、$A$ の各頂点が $B$ の全頂点と隣接する二部グラフ。
• 閉路グラフ $C_n$、道グラフ $P_n$: $n$ 頂点の閉路、$n$ 頂点の道だけからなるグラフ。

補題 2.5（歩道から道を取り出す）✓

$u$ から $v$ への歩道があれば、その歩道の頂点と辺だけを使う $u$ から $v$ への道がある。

証明（補題 2.5）

与えられた歩道の頂点と辺だけを使う $u$ から $v$ への歩道のうち、長さが最小のもの $W=v_0\cdots v_k$ を取ります（長さは非負整数なので、整列性 公理 3.1［証明の技術］ により最小のものがあります）。$i<j$ で $v_i=v_j$ となったとすると、$v_0\cdots v_iv_{j+1}\cdots v_k$ も条件を満たす歩道で、長さが $j-i\ge1$ だけ短くなり、最小性に反します。よって $W$ の頂点は相異なり、$W$ は道です。

∎

定義 2.6（連結成分・距離・直径・内周）↗

頂点 $u,v$ について、$u$ から $v$ への歩道があるとき $u\sim v$ と書く。長さ 0 の歩道、歩道の逆順、歩道の連結を考えれば、$\sim$ は同値関係である。同値類が誘導する部分グラフを $G$ の連結成分といい、その個数を $c(G)$ と書く。$c(G)=1$ のとき $G$ は連結であるという。

$u\sim v$ のとき、$u$ から $v$ への道の長さの最小値を距離 $d(u,v)$ という（補題 2.5 により、歩道の長さの最小値と言っても同じ）。連結グラフの距離の最大値を直径、$G$ に含まれる閉路の長さの最小値を内周という（閉路がなければ内周は $\infty$）。

異なる連結成分の頂点を結ぶ辺はありません（辺は長さ 1 の歩道です）。したがって $G$ は連結成分の非交和です。

3. 最長の道を取る論法

有限グラフでは、道の長さは $n-1$ 以下なので、最長の道が必ずあります。その端点 $v_0$ の隣接点は、すべて道の上になければなりません。道の外に隣接点 $w$ があれば、$w$ を先頭に付け足してもっと長い道ができるからです。極大な対象を取って、その端で何が起きているかを調べるというこの論法は、この章で 3 回、テーマ全体では何度も使います。最初の使用例を、省略せずに書きます。

命題 3.1（最小次数と長い道・長い閉路）✓

$\delta(G)\ge2$ ならば、$G$ は長さ $\delta(G)$ 以上の道と、長さ $\delta(G)+1$ 以上の閉路を含む。

証明（命題 3.1）

$\delta=\delta(G)$ とし、$G$ の最長の道 $P=v_0v_1\cdots v_k$ を取ります。

手順 1（端点の近傍は道の上にある）. $w\in N(v_0)$ が $P$ の上になかったとすると、$wv_0v_1\cdots v_k$ は頂点が相異なる歩道、すなわち長さ $k+1$ の道で、$P$ が最長であることに反します。よって $N(v_0)\subseteq\{v_1,\dots,v_k\}$ です。

手順 2（添字の最大値を見る）. $v_0$ と隣接する $v_i$ の添字 $i$ の最大値を $i_0$ とします。$N(v_0)$ は $\{v_1,\dots,v_{i_0}\}$ に含まれ、$|N(v_0)|=d(v_0)\ge\delta$ なので、$i_0\ge\delta$ です。とくに $k\ge i_0\ge\delta$ で、$P$ は長さ $\delta$ 以上の道です。

手順 3（閉じる）. $v_0v_1\cdots v_{i_0}v_0$ は、$v_0v_{i_0}\in E(G)$ なので閉じた歩道で、$v_0,\dots,v_{i_0}$ は相異なり、長さは $i_0+1\ge\delta+1\ge3$ です。これは長さ $\delta+1$ 以上の閉路です。

∎

例 3.2（評価は最良）

$K_{\delta+1}$ は最小次数 $\delta$ で、頂点が $\delta+1$ 個しかないので、道の長さは $\delta$ 以下、閉路の長さは $\delta+1$ 以下です。したがって 命題 3.1 の 2 つの下界は、どちらもこれ以上よくできません。また $\delta=1$ では閉路の主張は成り立ちません（道グラフ $P_2$ は閉路を含みません）。

次の定理は、二部グラフという大域的な性質を、閉路の長さという目に見える条件で言い換えます。第 2 章のマッチングの理論は、この定理を通して「奇閉路がない」ことを使います。

定理 3.3（二部グラフと奇閉路）✓

グラフ $G$ が二部グラフであるためには、$G$ が長さが奇数の閉路を含まないことが必要十分である。

十分性の方針は、1 つの頂点 $r$ からの距離の偶奇で頂点を 2 組に分けることです。同じ組の中に辺があると、そこから $r$ に戻る 2 本の最短の道と合わせて奇数長の閉路ができてしまう、という流れで示します。下の図は、距離 2 の頂点どうしを辺 $cd$ で結んだ場合で、$r,a,c,d,b$ の長さ 5 の閉路ができています。

根 r からの距離で層に並べた図。同じ層（距離 2）の頂点 c, d を結ぶ辺（色つき）があると、長さ 5 の奇閉路 r, a, c, d, b ができる

証明（定理 3.3）

必要性. $(A,B)$ を二部分割とし、$v_0v_1\cdots v_k$（$v_k=v_0$）を閉路とします。どの辺も $A$ と $B$ を結ぶので、$v_0\in A$ なら $v_1\in B$、$v_2\in A$、……と交互に並び、$v_i\in A$ となるのは $i$ が偶数のときです（$v_0\in B$ のときも同様）。$v_k=v_0$ なので $k$ は偶数です。

十分性. $G$ が奇閉路を含まないとします。各連結成分の二部分割を合わせれば $G$ の二部分割になる（成分の間に辺はない）ので、$G$ は連結としてかまいません。頂点 $r$ を固定し、

$$A=\{v: d(r,v)\text{ は偶数}\},\qquad B=\{v: d(r,v)\text{ は奇数}\}$$

と置きます。$A$ の中、または $B$ の中に辺 $xy$ があったとして矛盾を導きます。このとき $d(r,x)\equiv d(r,y)\pmod 2$ です。

$r$ から $x$ への最短の道 $P$ と、$r$ から $y$ への最短の道 $Q$ を取ります。$P$ の頂点のうち $Q$ の上にもあるもので、$P$ に沿って最も $x$ に近いものを $z$ とします（$r$ は両方の上にあるので、そのような頂点はあります）。

最短の道の部分は最短です。実際、$rPz$ の長さが $d(r,z)$ より大きければ、$r$ から $z$ への最短の道に $zPx$ をつないだ歩道は $P$ より短く、補題 2.5 から $P$ より短い $r$ から $x$ への道ができて矛盾します。$Q$ についても同じです。よって $zPx$ の長さは $d(r,x)-d(r,z)$、$zQy$ の長さは $d(r,y)-d(r,z)$ です。

$z$ の選び方から、$zPx$ の $z$ 以外の頂点は $Q$ の上にありません。したがって、$z$ から $zPx$ で $x$ に進み、辺 $xy$ を渡り、$zQy$ を逆にたどって $z$ に戻る閉じた歩道は、$z$ 以外に頂点の重複がなく、その長さは

$$\bigl(d(r,x)-d(r,z)\bigr)+1+\bigl(d(r,y)-d(r,z)\bigr)\equiv 2d(r,x)-2d(r,z)+1\equiv1\pmod2$$

です。長さが 1 だとすると $x=z=y$ となり、$xy$ が辺であること（$x\ne y$）に反します。よって長さは 3 以上の奇数で、これは奇閉路です。仮定に反するので、どの辺も $A$ と $B$ を結び、$(A,B)$ は二部分割です。

∎

4. 木と橋

定義 4.1（橋・切断点）↗

辺 $e=uv$ が $G$ の橋であるとは、$u$ と $v$ が $G-e$ の異なる連結成分に属することをいう。頂点 $v$ が切断点であるとは、$c(G-v)>c(G)$ となることをいう。

$e=uv$ が橋なら、$u,v$ を含んでいた $G$ の連結成分が $G-e$ ではちょうど 2 つに分かれ、$c(G-e)=c(G)+1$ です（$e$ を使う歩道は、$e$ を渡る直前までを見れば $u$ か $v$ のどちらかに $G-e$ の中で届くからです）。橋でなければ $c(G-e)=c(G)$ です。

命題 4.2（橋の特徴づけ）✓

辺 $e=uv$ が $G$ の橋であるためには、$e$ が $G$ のどの閉路にも乗らないことが必要十分である。

証明（命題 4.2）

対偶の形で「$e$ が橋でない $\iff$ $e$ を通る閉路がある」を示します。

$e$ が橋でないとすると、$G-e$ に $u$ から $v$ への歩道があり、補題 2.5 から $G-e$ に $u$ から $v$ への道 $P=u\cdots v$ があります。$P$ は $e$ を使わず、$G$ は単純なので $P$ の長さは 2 以上です。$P$ の終点 $v$ から辺 $e$ で $u$ に戻ると、頂点の重複のない長さ 3 以上の閉じた歩道、すなわち $e$ を通る閉路ができます。

逆に、$e$ を通る閉路 $C$ があれば、$C$ から $e$ を除いたものは $G-e$ の中の $u$ から $v$ への道なので、$u$ と $v$ は $G-e$ の同じ連結成分に属し、$e$ は橋ではありません。

∎

補題 4.3（相異なる 2 本の道は閉路を生む）✓

$G$ に $u$ から $v$ への相異なる 2 本の道があれば、$G$ は閉路を含む。

証明の考え方は、2 本の道が最初に分かれる場所と、そのあと最初に合流する場所を取り、その間の 2 つの道部分をつなげて閉路にすることです。

証明（補題 4.3）

2 本の道を $P=p_0p_1\cdots p_k$、$Q=q_0q_1\cdots q_l$（$p_0=q_0=u$、$p_k=q_l=v$）とします。一方が他方の先頭部分になることはありません（たとえば $k<l$ で $p_j=q_j$（$j\le k$）なら $q_k=v=q_l$ となり、$Q$ の頂点が相異なることに反します）。$P\ne Q$ なので、$p_{i+1}\ne q_{i+1}$ となる最小の $i$ があり、$i<k$、$i<l$、$p_j=q_j$（$j\le i$）です。

$p_k=q_l$ なので、$j>i$ で $p_j\in\{q_{i+1},\dots,q_l\}$ となるものがあります。そのうち最小の $j$ を取り、$p_j=q_h$（$h>i$）とします。道 $p_iPp_j$ の内部の頂点 $p_{i+1},\dots,p_{j-1}$ は、$j$ の最小性から $q_{i+1},\dots,q_l$ のどれとも異なり、$P$ の頂点が相異なることから $p_i=q_i$ とも異なります。したがって、$p_iPp_j$ を進んで $q_iQq_h$ を逆に戻る閉じた歩道は、頂点の重複がありません。長さは $(j-i)+(h-i)\ge2$ で、長さ 2 になるのは $j=h=i+1$ のときだけですが、そのとき $p_{i+1}=q_{i+1}$ となって $i$ の選び方に反します。よって長さ 3 以上の閉路です。

∎

定理 4.4（木の同値な特徴づけ）✓

$n\ge1$ 頂点のグラフ $T$ について、次の 6 条件は同値である。

1. $T$ は木である（連結で、閉路を含まない）。
2. $T$ のどの 2 頂点も、ちょうど 1 本の道で結ばれる。
3. $T$ は連結で、どの辺も橋である（極小連結）。
4. $T$ は閉路を含まず、隣接しないどの 2 頂点 $u,v$ についても $T+uv$ は閉路を含む（極大非閉路的）。
5. $T$ は連結で、辺の数が $n-1$ である。
6. $T$ は閉路を含まず、辺の数が $n-1$ である。

証明（定理 4.4）

$(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1)$、$(1)\Rightarrow(5)\Rightarrow(6)\Rightarrow(1)$、$(1)\Leftrightarrow(4)$ の順に示します。

$(1)\Rightarrow(2)$. 連結なので、2 頂点を結ぶ歩道があり、補題 2.5 から道があります。道が 2 本あれば 補題 4.3 から閉路ができ、(1) に反します。

$(2)\Rightarrow(3)$. どの 2 頂点も道で結ばれるので連結です。辺 $e=uv$ について、長さ 1 の道 $uv$ は $u$ から $v$ への道です。$T-e$ に $u$ から $v$ への道があれば、それは $e$ を使わないので $uv$ と異なる 2 本目の道になり、(2) に反します。よって $u$ と $v$ は $T-e$ の異なる成分に属し、$e$ は橋です。

$(3)\Rightarrow(1)$. 閉路があれば、その上の辺は 命題 4.2 から橋でなく、(3) に反します。

$(1)\Rightarrow(5)$. 補題 2.2［グラフと行列式］ の 1 で成分数を $c=1$ とすれば、辺の数は $n-1$ です。

$(5)\Rightarrow(6)$. $T$ が閉路を含むとします。閉路の上の辺は橋でない（命題 4.2）ので、除いても連結のままです。閉路がなくなるまでこれを繰り返すと（辺は有限本なので必ず止まります）、$n$ 頂点の連結で閉路のないグラフ、すなわち木が得られ、その辺の数は $n-1$ より真に小さくなります。これは $(1)\Rightarrow(5)$ に反します。

$(6)\Rightarrow(1)$. $T$ は森なので、補題 2.2［グラフと行列式］ の 1 から辺の数は $n-c(T)$ です。これが $n-1$ に等しいので $c(T)=1$、すなわち連結です。

$(1)\Rightarrow(4)$. 隣接しない $u,v$ に対し、$T$ は連結なので $u$ から $v$ への道 $P$ があり、その長さは 2 以上です。$P$ に辺 $uv$ を足すと $T+uv$ の閉路になります。

$(4)\Rightarrow(1)$. 連結性を示します。$u\ne v$ とします。隣接していれば歩道 $uv$ があります。隣接していなければ $T+uv$ は閉路 $C$ を含み、$T$ は閉路を含まないので $C$ は辺 $uv$ を通ります。$C$ から $uv$ を除いたものは $T$ の中の $u$ から $v$ への道です。

∎

系 4.5（全域木の存在）✓

連結グラフは全域木をもつ。とくに、$n$ 頂点の連結グラフの辺の数は $n-1$ 以上である。

証明（系 4.5）

$G$ を連結グラフとします。$G$ の連結な全域部分グラフ（$G$ 自身がその 1 つ）のうち、辺の数が最小のもの $T$ を取ります。$T$ の辺 $e$ が橋でなければ、$T-e$ も連結な全域部分グラフで辺が 1 本少なく、最小性に反します。よって $T$ は連結でどの辺も橋であり、定理 4.4 の $(3)\Rightarrow(1)$ から木です。全頂点を含むので全域木です。後半は、同じ定理の (5) から $|E(G)|\ge|E(T)|=n-1$ です。

∎

例 4.6（木の個数）

頂点集合 $\{1,\dots,n\}$ 上の木は $n^{n-2}$ 個あります（Cayley の公式、定理 5.4［数え上げと母関数］）。$n=4$ なら $16$ 個で、内訳は道 $P_4$ の形のものが $4!/2=12$ 個、1 頂点が他の 3 頂点と隣接する星の形のものが中心の選び方の $4$ 個です。どちらも辺は $3=n-1$ 本で、定理 4.4 の (5) と合っています。

5. Euler 回路

この節に限り、多重辺を許します（同じ 2 頂点を結ぶ辺が複数本あってよい、ということです。Königsberg のグラフには多重辺があります）。握手補題（補題 2.2）は多重グラフでも成り立ちます。

定義 5.1（Euler 回路・Euler 小道）↗

グラフ $G$ のすべての辺をちょうど 1 回ずつ使う小道を Euler 小道、閉じた Euler 小道を Euler 回路という。

小道が各頂点に接続する辺を何本使うかを、先に数えておきます。

補題 5.2（小道が頂点で使う辺の数）✓

$W=v_0e_1v_1\cdots e_kv_k$ を小道とする。頂点 $w$ に接続する辺のうち $W$ が使うものの本数は

$$2\cdot\#\{i: 1\le i\le k-1,\ v_i=w\}+[v_0=w]+[v_k=w]$$

である（$[\ \cdot\ ]$ は条件が真なら 1、偽なら 0）。したがって、$W$ が閉じていればどの頂点でも偶数であり、閉じていなければ両端点 $v_0,v_k$ でだけ奇数である。

証明（補題 5.2）

辺 $e_1,\dots,e_k$ は相異なり、$e_i$ の端点は $v_{i-1}$ と $v_i$（相異なる）です。よって $w$ に接続する $W$ の辺の本数は

$$\#\{i: 1\le i\le k,\ v_{i-1}=w\}+\#\{i:1\le i\le k,\ v_i=w\}$$

です。第 1 項は添字 $0,\dots,k-1$ のうち $v_j=w$ となるものの個数、第 2 項は添字 $1,\dots,k$ のうちの個数なので、内部の添字 $1,\dots,k-1$ は 2 回、両端の添字 $0$ と $k$ は 1 回ずつ数えられ、主張の式になります。$v_0=v_k$ なら $[v_0=w]+[v_k=w]$ は 0 か 2 で、全体は偶数です。$v_0\ne v_k$ なら、$w$ が端点のときだけこの和が 1 になります。

∎

定理 5.3（Euler の定理）✓

辺を 1 本以上もつ連結な（多重辺を許す）グラフ $G$ が Euler 回路をもつためには、すべての頂点の次数が偶数であることが必要十分である。

十分性の方針は、閉じた小道のうち最も長いものを取り、まだ使っていない辺が残っているなら、そこから寄り道の閉じた小道を継ぎ足してさらに長くできる、と示すことです。最長のものを取ったので、そのような継ぎ足しは起こりえず、使っていない辺はない、という結論になります。

証明（定理 5.3）

必要性. Euler 回路は閉じた小道で、すべての辺を使います。補題 5.2 から、各頂点に接続する辺の総数、すなわち次数は偶数です。

十分性（Hierholzer の構成）. すべての次数が偶数とします。

手順 1: 延ばせなくなった小道は閉じている. すべての次数が偶数であるグラフ $H$ の中で、小道 $W$ がこれ以上延ばせない（終点 $w$ に接続する辺をすべて使い切っている）とします。$W$ が閉じていなければ、補題 5.2 から $W$ は $w$ に接続する辺を奇数本使っています。$d_H(w)$ は偶数なので、使っていない辺が $w$ に残っており、延ばせることになって矛盾します。よって $W$ は閉じています。

手順 2: 最長の閉じた小道を取る. $G$ の閉じた小道のうち、長さが最大のもの $W=v_0e_1v_1\cdots e_kv_0$ を取ります。$G$ には辺があり、1 つの辺から始めて延ばせなくなるまで延ばした小道は手順 1 から閉じているので、$k\ge1$ です。$W$ がすべての辺を使っていることを示せば、$W$ が Euler 回路です。

手順 3: 使い残しがあれば継ぎ足せる. $W$ が使っていない辺があるとします。$W$ の上の頂点に接続する未使用の辺 $f$ があることを示します。$W$ が全頂点を通るなら、未使用の辺はどれも $W$ の頂点に接続します。そうでなければ、$G$ は連結なので、$W$ の上の頂点から $W$ の外の頂点への道があり、その道が初めて $W$ の頂点集合の外に出る辺 $f=xy$（$x$ は $W$ の上、$y$ は外）は、$y$ を通らない $W$ には使われていません。

$G$ から $W$ の辺をすべて除いたグラフを $G'$ とします。補題 5.2 から、$W$ は各頂点で偶数本の辺を使っているので、$G'$ の次数もすべて偶数です。$G'$ の中で、$x=v_i$ から辺 $f$ で出発して延ばせなくなるまで延ばした小道 $W'$ は、手順 1 から閉じていて、$x$ に戻ります。$W$ を $v_i$ まで進み、そこで $W'$ を一周してから $W$ の残りを進めば、$W$ と $W'$ は辺を共有しないので、長さ $k+|W'|>k$ の閉じた小道ができます。これは $W$ の最大性に反します。

∎

系 5.4（閉じていない Euler 小道）✓

連結な（多重辺を許す）グラフ $G$ と相異なる頂点 $u,v$ について、$u$ から $v$ への Euler 小道があるためには、次数が奇数の頂点が $u$ と $v$ のちょうど 2 個であることが必要十分である。したがって、連結グラフが Euler 小道をもつのは、奇数次の頂点が 0 個または 2 個のときである。

証明（系 5.4）

必要性. $u$ から $v$ への Euler 小道は閉じておらず、すべての辺を使うので、補題 5.2 から次数が奇数になるのは端点 $u,v$ だけです。

十分性. $G$ に新しい頂点 $z$ と 2 本の辺 $zu$、$zv$ を足したグラフ $G^+$ を作ります。$G^+$ は連結で、$u$ と $v$ の次数が 1 ずつ増え、$d(z)=2$ なので、すべての次数が偶数です。定理 5.3 から $G^+$ は Euler 回路をもちます。回路は $z$ を 1 回だけ通り、そこで辺 $uz$ と $zv$ を続けて使います。回路を $z$ から始まるように回し、最初の辺 $zv$（または $zu$）と最後の辺を除くと、$G$ のすべての辺を使う $u$ と $v$ を結ぶ小道が残ります。

最後の主張は、握手補題（補題 2.2）から奇数次の頂点の個数は偶数なので、Euler 小道が閉じている場合（定理 5.3、0 個）と閉じていない場合（2 個）を合わせたものです。

∎

例 5.5（Königsberg の橋）

冒頭の図のグラフは、次数が $5,3,3,3$ で、奇数次の頂点が 4 個あります。系 5.4 から、出発点に戻る散歩道はもちろん、戻らなくてよいとしてもすべての橋を 1 回ずつ渡る散歩道はありません。橋を 1 本足して奇数次の頂点を 2 個にすれば、その 2 頂点を端点とする Euler 小道ができます。

例 5.6（de Bruijn 列）

長さ 8 の巡回的な 0-1 列 $00010111$ は、連続する 3 文字として $000,001,010,101,011,111,110,100$ をこの順に含み、長さ 3 の 0-1 列の全 8 通りがちょうど 1 回ずつ現れます。このような列は、有向グラフの Euler 回路として作れます。長さ 2 の 0-1 列 $ab$ を頂点とし、長さ 3 の列 $abc$ ごとに $ab$ から $bc$ への有向辺を引くと、どの頂点も入る辺が 2 本、出る辺が 2 本です。有向グラフでも「入次数と出次数が各頂点で等しく、辺を無視して連結」なら有向 Euler 回路があることは、定理 5.3 の証明の「偶数」を「入る本数と出る本数が等しい」に読み替えれば同じ手順で示せます。上の列は、有向 Euler 回路 $00\to00\to01\to10\to01\to11\to11\to10\to00$ の辺のラベルの先頭の文字を順に読んだものです。

6. Hamilton 閉路

この節からは再び単純グラフだけを考えます。

定義 6.1（Hamilton 閉路・Hamilton 道）↗

グラフ $G$ のすべての頂点を通る閉路を Hamilton 閉路、すべての頂点を通る道を Hamilton 道という。Hamilton 閉路をもつグラフを Hamilton グラフという。

6.1. 必要条件

命題 6.2（Hamilton 閉路の必要条件）✓

$G$ が Hamilton 閉路をもつならば、空でないどの $S\subseteq V(G)$ についても $c(G-S)\le|S|$ である。

証明（命題 6.2）

$C$ を Hamilton 閉路とし、向きを 1 つ決めます。$S=V(G)$ なら $G-S$ は頂点をもたず $c(G-S)=0$ です。$S\ne V(G)$ とします。$C$ の上で $S$ に入らない頂点が連続して並ぶ極大な区間を弧と呼びます。各弧は $C$ の一部なので連結で、弧を向きに沿って進んだ直後の頂点は $S$ の元です（$S\ne\varnothing$ なので、弧は必ず終わります）。この対応「弧 $\mapsto$ 直後の $S$ の頂点」は単射なので、弧の個数は $|S|$ 以下です。$G-S$ の頂点はどれかの弧に属し、各弧は $G-S$ の 1 つの連結成分に含まれるので、$G-S$ の連結成分の個数は弧の個数以下、したがって $|S|$ 以下です。

∎

例 6.3（完全二部グラフ $K_{k,k+1}$）

$k\ge1$ とし、$K_{k,k+1}$ の小さいほうの側を $S$（$|S|=k$）とします。$G-S$ は辺のない $k+1$ 頂点のグラフで、$c(G-S)=k+1>|S|$ です。命題 6.2 から $K_{k,k+1}$ は Hamilton 閉路をもちません。頂点数は $n=2k+1$、最小次数は $\delta=k=(n-1)/2$ です。次の Dirac の定理の仮定 $\delta\ge n/2$ は、$(n-1)/2$ に下げることができないことが分かります。

6.2. Dirac の定理と Ore の定理

十分条件の証明の核は、次の補題です。Hamilton 道の両端点に 命題 3.1 と同じ見方を当て、端点の隣接点が道のどこにあるかを添字で数えます。

補題 6.4（端点の次数の和が大きい Hamilton 道は閉じられる）✓

$n\ge3$ 頂点のグラフ $G$ が Hamilton 道 $v_1v_2\cdots v_n$ をもち、$d(v_1)+d(v_n)\ge n$ ならば、$G$ は Hamilton 閉路をもつ。

方針は、$v_1$ の隣接点の位置と $v_n$ の隣接点の位置が、数え上げによってどこかで重なることを示し、その位置で道をつなぎ直して閉じることです。たとえば $n=5$ の道 $v_1v_2v_3v_4v_5$ に辺 $v_1v_3$ と $v_2v_5$ があれば、$v_1v_3v_4v_5v_2v_1$ が全頂点を 1 回ずつ通る閉路になります。

証明（補題 6.4）

$v_1v_n\in E(G)$ なら $v_1v_2\cdots v_nv_1$ が Hamilton 閉路です。$v_1v_n\notin E(G)$ とし、添字の集合

$$S=\{i: v_1v_{i+1}\in E(G)\},\qquad T=\{i: v_iv_n\in E(G)\}$$

を考えます。$v_1$ の隣接点は $v_2,\dots,v_{n-1}$ の中にあるので $S\subseteq\{1,\dots,n-2\}$、$|S|=d(v_1)$ です。$v_n$ の隣接点も $v_2,\dots,v_{n-1}$ の中にあるので $T\subseteq\{2,\dots,n-1\}$、$|T|=d(v_n)$ です。$S\cup T\subseteq\{1,\dots,n-1\}$ なので

$$|S\cap T|=|S|+|T|-|S\cup T|\ge n-(n-1)=1$$

となり、$i\in S\cap T$ が取れます（$2\le i\le n-2$）。このとき $v_1v_{i+1}$ と $v_iv_n$ は辺なので、

$$v_1\,v_{i+1}\,v_{i+2}\cdots v_n\,v_i\,v_{i-1}\cdots v_2\,v_1$$

は全頂点を 1 回ずつ通る閉じた歩道、すなわち Hamilton 閉路です。

∎

定理 6.5（Ore の定理）✓

$n\ge3$ 頂点のグラフ $G$ で、隣接しないどの 2 頂点 $u\ne v$ についても $d(u)+d(v)\ge n$ ならば、$G$ は Hamilton 閉路をもつ。

証明（定理 6.5）

連結性. 隣接しない $u\ne v$ について、$N(u)$ と $N(v)$ はどちらも $V(G)\setminus\{u,v\}$（$n-2$ 個）に含まれ、$|N(u)|+|N(v)|\ge n>n-2$ なので共通の元をもちます。よって $u$ と $v$ は長さ 2 の道で結ばれ、$G$ は連結です。

最長の道. $G$ の最長の道 $P=v_1\cdots v_k$ を取ります。$G$ は連結で $n\ge3$ なので $k\ge3$ です（連結なら辺があり、辺 $xy$ の外の頂点への道の上で、最初に $\{x,y\}$ の外に出る辺を足せば 3 頂点の道ができます）。命題 3.1 の証明の手順 1 と同じく、$v_1$ と $v_k$ の隣接点はすべて $P$ の上にあります。

$P$ の頂点集合上の閉路. $H=G[\{v_1,\dots,v_k\}]$ とします。$H$ の中での $v_1,v_k$ の次数は $G$ の中での次数と同じです。$v_1v_k\in E(G)$ なら $v_1\cdots v_kv_1$ が $H$ の Hamilton 閉路です。そうでなければ、仮定から $d_H(v_1)+d_H(v_k)=d(v_1)+d(v_k)\ge n\ge k$ なので、補題 6.4 を $H$ とその Hamilton 道 $P$ に使って、$H$ の Hamilton 閉路 $C$ が得られます。

$k=n$ であること. $k<n$ とします。$G$ は連結なので、$C$ の外の頂点 $w$ で、$C$ の上のある頂点 $x$ と隣接するものがあります。$C$ の上で $x$ の隣の頂点を $x'$ とすると、$C$ から辺 $xx'$ を除いた道（$x'$ から $x$ まで $C$ の全頂点を通る）の終点 $x$ に $w$ を付け足して、$k+1$ 頂点の道ができます。これは $P$ が最長であることに反します。よって $k=n$ で、$C$ は $G$ の Hamilton 閉路です。

∎

定理 6.6（Dirac の定理）✓

$n\ge3$ 頂点のグラフ $G$ が $\delta(G)\ge n/2$ を満たせば、$G$ は Hamilton 閉路をもつ。

証明（定理 6.6）

どの 2 頂点 $u,v$ についても $d(u)+d(v)\ge 2\delta(G)\ge n$ です。定理 6.5 の仮定が満たされるので、$G$ は Hamilton 閉路をもちます。

∎

6.3. Bondy–Chvátal の閉包

補題 6.4 をよく見ると、次数の和が大きい非隣接な 2 頂点の間には、辺を足しても Hamilton 性が変わらないことが分かります。これを繰り返したものが閉包です。

補題 6.7（辺を 1 本足しても Hamilton 性は変わらない）✓

$n\ge3$ 頂点のグラフ $G$ の隣接しない 2 頂点 $u,v$ が $d(u)+d(v)\ge n$ を満たすとする。このとき、$G$ が Hamilton 閉路をもつことと $G+uv$ が Hamilton 閉路をもつことは同値である。

証明（補題 6.7）

$G$ の Hamilton 閉路は $G+uv$ の Hamilton 閉路です。逆に、$G+uv$ の Hamilton 閉路 $C$ を取ります。$C$ が辺 $uv$ を使わなければ $C$ は $G$ の Hamilton 閉路です。使うなら、$C$ から $uv$ を除いたものは $G$ の Hamilton 道で、端点は $u$ と $v$ です。$d(u)+d(v)\ge n$ なので、補題 6.4 から $G$ は Hamilton 閉路をもちます。

∎

定義 6.8（閉包）↗

$n$ 頂点のグラフ $G$ から始めて、「隣接しない 2 頂点 $u,v$ で、現在のグラフでの次数の和が $n$ 以上のものがあれば、辺 $uv$ を足す」という操作を、できなくなるまで繰り返して得られるグラフを $G$ の閉包といい、$\operatorname{cl}(G)$ と書く。

定理 6.9（Bondy–Chvátal の閉包定理）✓

$n\ge3$ 頂点のグラフ $G$ について、次が成り立つ。

1. $\operatorname{cl}(G)$ は、辺を足す順序によらずに定まる。
2. $G$ が Hamilton 閉路をもつことと、$\operatorname{cl}(G)$ が Hamilton 閉路をもつことは同値である。
3. とくに $\operatorname{cl}(G)=K_n$ ならば、$G$ は Hamilton 閉路をもつ。

証明（定理 6.9）

1. 辺 $e_1,\dots,e_r$ をこの順に足して操作が止まったグラフを $G_1$、別の順序で $f_1,\dots,f_s$ を足して止まったグラフを $G_2$ とします。すべての $i$ について $e_i\in E(G_2)$ であることを、$i$ についての帰納法（定理 4.3［証明の技術］）で示します。$e_1,\dots,e_{i-1}\in E(G_2)$ とすると、$H=G+e_1+\cdots+e_{i-1}$ は $G_2$ の部分グラフです。$e_i=uv$ は $H$ で足せる辺なので $d_H(u)+d_H(v)\ge n$、したがって $d_{G_2}(u)+d_{G_2}(v)\ge n$ です。$G_2$ ではもう操作ができないので、$u$ と $v$ は $G_2$ で隣接していなければならず、$e_i\in E(G_2)$ です。よって $G_1\subseteq G_2$ で、役割を入れ替えれば $G_2\subseteq G_1$、すなわち $G_1=G_2$ です。

2. 辺を 1 本足すたびに 補題 6.7 を使えば、$G$、$G+e_1$、$G+e_1+e_2$、……、$\operatorname{cl}(G)$ の Hamilton 性はすべて同値です。

3. $n\ge3$ のとき $K_n$ は Hamilton 閉路（頂点を任意の順に並べて一周する）をもつので、2 から従います。

∎

Ore の定理は「1 回目の操作ですべての非隣接対に辺が入り、$\operatorname{cl}(G)=K_n$ になる」場合にあたります。次の系は、次数の小さい頂点がいくつかあっても、次数の大きい頂点が十分あれば閉包が完全グラフになることを保証します。

系 6.10（Chvátal の次数列条件）✓

$n\ge3$ 頂点のグラフ $G$ の次数を小さい順に $d_1\le d_2\le\cdots\le d_n$ とする。$1\le i<n/2$ であるすべての $i$ について

$$d_i>i\quad\text{または}\quad d_{n-i}\ge n-i$$

が成り立てば、$G$ は Hamilton 閉路をもつ。

証明の流れは 3 段です。まず、閉包にしても次数列の条件が保たれることを見ます。次に、閉包が完全グラフでないと仮定し、隣接しない 2 頂点のうち次数の和が最大のものに注目します。するとその次数から、条件に反する次数の小さい頂点が十分多く見つかり、矛盾します。最後に、閉包が完全グラフなら Bondy–Chvátal の閉包定理から Hamilton 閉路があります。

証明（系 6.10）

$H=\operatorname{cl}(G)$ とし、$H$ の次数を小さい順に $d_1'\le\cdots\le d_n'$ とします。

$H$ も同じ条件を満たす. $G$ で次数が $d_j$ 以上の頂点は少なくとも $n-j+1$ 個あり、辺を足しても次数は減らないので、$H$ でも次数が $d_j$ 以上の頂点が $n-j+1$ 個以上あります。よって $d_j'\ge d_j$ で、$H$ の次数列も仮定の条件を満たします。

$H=K_n$ であること. $H$ が完全グラフでないとして矛盾を導きます。$H$ で隣接しない 2 頂点 $u,v$ のうち、$d_H(u)+d_H(v)$ が最大のものを取り、$d_H(u)\le d_H(v)$ とします。$H$ ではもう辺を足せないので $d_H(u)+d_H(v)\le n-1$ で、$i=d_H(u)$ と置くと $2i\le n-1$、すなわち $i<n/2$ です。

$i=0$ の場合. $u$ は $H$ で孤立しているので $d_1'=0\le1$ です。また、どの頂点も $u$ と隣接しないので次数は $n-2$ 以下で、$d_{n-1}'\le n-2<n-1$ です。$n\ge3$ から $1<n/2$ なので、これは条件の $i=1$ の場合に反します。

$i\ge1$ の場合. $v$ と異なり $v$ に隣接しない頂点の集合を $S$ とします。$|S|=n-1-d_H(v)\ge d_H(u)=i$ です。$w\in S$ は $v$ と隣接しないので、$u,v$ の選び方から $d_H(w)+d_H(v)\le d_H(u)+d_H(v)$、すなわち $d_H(w)\le i$ です。次数が $i$ 以下の頂点が $i$ 個以上あるので、$d_i'\le i$ です。

同様に、$u$ と異なり $u$ に隣接しない頂点の集合を $T$ とすると、$|T|=n-1-i$ で、$w\in T$ は $d_H(w)\le d_H(v)\le n-1-i$ を満たします。$u$ 自身も $d_H(u)=i\le n-1-i$ です。次数が $n-1-i$ 以下の頂点が $T\cup\{u\}$ の $n-i$ 個以上あるので、$d_{n-i}'\le n-1-i<n-i$ です。

これは $H$ の次数列が $i$ について条件を満たすことに反します。

以上から $H=K_n$ で、定理 6.9 の 3 から $G$ は Hamilton 閉路をもちます。

∎

例 6.11（Ore の条件は満たさないが Chvátal の条件を満たすグラフ）

頂点 $1,\dots,6$、辺 $14,15,23,24,26,35,36,45,46,56$ のグラフを考えます。次数は順に $2,3,3,4,4,4$ です。頂点 $1$ と $2$ は隣接せず $d(1)+d(2)=5<6$ なので、Ore の定理も Dirac の定理も使えません。一方、次数列 $(2,3,3,4,4,4)$ は $i=1$ で $d_1=2>1$、$i=2$ で $d_2=3>2$ を満たすので、系 6.10 から Hamilton 閉路があります。実際 $1,4,2,3,6,5,1$ がそうです（辺 $14,42,23,36,65,51$ はすべてあります）。

6.4. 例：Petersen グラフ・超立方体・騎士の巡回

例 6.12（Petersen グラフは Hamilton 閉路をもたない）

Petersen グラフは、外側の 5 頂点 $u_0,\dots,u_4$ と内側の 5 頂点 $w_0,\dots,w_4$ をもち、辺は外側の五角形 $u_iu_{i+1}$、スポーク $u_iw_i$、内側の星形 $w_iw_{i+2}$（添字は $5$ を法とする）の 15 本です。3-正則で、$n=10$ です。

Petersen グラフ。外側の五角形、5 本のスポーク、内側の星形からなる

Hamilton 閉路 $C$ があるとして矛盾を導きます。$C$ は各頂点で 2 本の辺を使うので、各頂点で使わない辺がちょうど 1 本あります。$C$ が使わない 5 本の辺の集合を $M$ とすると、$M$ の辺はどの 2 本も端点を共有せず、全 10 頂点を覆います。

$C$ は閉路なので、外側の頂点集合と内側の頂点集合の間を行き来する回数、すなわち $C$ が使うスポークの本数 $s$ は偶数です。$s=0$ だと $C$ は外側から内側に移れず全頂点を通れないので、$s=2$ または $s=4$ です。

$s=4$ の場合. 使わないスポークは 1 本で、対称性から $u_0w_0$ としてかまいません。$M$ の残り 4 本は、外側の辺 2 本で $u_1,u_2,u_3,u_4$ を、内側の辺 2 本で $w_1,w_2,w_3,w_4$ を覆います。$u_1,\dots,u_4$ の間の外側の辺は $u_1u_2,u_2u_3,u_3u_4$ だけなので、覆い方は $\{u_1u_2,u_3u_4\}$ に限ります。$w_1,\dots,w_4$ の間の内側の辺は $w_1w_3,w_2w_4,w_1w_4$ だけで、$w_1w_4$ を選ぶと $w_2,w_3$ が残り（$w_2w_3$ は辺でない）覆えないので、覆い方は $\{w_1w_3,w_2w_4\}$ に限ります。このとき $C$ が使う辺のうち $u_0u_1,\ u_1w_1,\ w_1w_4,\ w_4u_4,\ u_4u_0$ の 5 本は、それだけで長さ 5 の閉路をなします。$C$ は長さ 10 の閉路なので、真の部分として閉路を含むことはなく、矛盾です。

$s=2$ の場合. 使わないスポークは 3 本で、$M$ の残り 2 本は外側の辺 1 本と内側の辺 1 本です。外側の辺 $u_iu_{i+1}$ は、スポークを $C$ に使われている 2 つの外側の頂点を覆うので、使われているスポークは $u_iw_i$ と $u_{i+1}w_{i+1}$ です。すると $M$ の内側の辺は $w_i$ と $w_{i+1}$ を覆わなければなりませんが、$w_iw_{i+1}$ は内側の星形の辺ではありません。矛盾です。

どちらの場合も矛盾するので、Petersen グラフは Hamilton 閉路をもちません。一方、どの空でない $S$ についても $c(G-S)\le|S|$ が成り立つことが確かめられるので、命題 6.2 の条件は十分条件ではありません。

例 6.13（超立方体と Gray 符号）

長さ $n$ の 0-1 列を頂点とし、ちょうど 1 か所だけ異なる 2 つの列を隣接させたグラフを超立方体 $Q_n$ といいます。$Q_n$ は $n$-正則で $2^n$ 頂点をもち、$1$ の個数の偶奇で分ければ二部グラフです。$n\ge2$ なら $Q_n$ は Hamilton 閉路をもちます。$n$ についての帰納法（定理 3.2［証明の技術］）で示します。$Q_2$ では $00,01,11,10$ が Hamilton 閉路です。$Q_n$ の Hamilton 閉路 $x_1,x_2,\dots,x_N$（$N=2^n$）があれば、

$$0x_1,\ 0x_2,\ \dots,\ 0x_N,\ 1x_N,\ 1x_{N-1},\ \dots,\ 1x_1$$

は $Q_{n+1}$ の Hamilton 閉路です（隣り合う列は 1 か所だけ異なり、最後の $1x_1$ と最初の $0x_1$ も先頭だけが異なります）。$n=3$ なら $000,001,011,010,110,111,101,100$ で、これは回転角の符号化などに使われる Gray 符号です。$\delta(Q_n)=n$ は $n\ge3$ で $2^n/2$ よりはるかに小さいので、Dirac の条件は必要条件からは遠いことも分かります。

例 6.14（騎士の巡回（小さい盤））

$a\times b$ のチェス盤のマスを頂点とし、騎士（ナイト）が 1 手で移れる 2 マスを隣接させたグラフの Hamilton 閉路を、閉じた騎士の巡回といいます。騎士は 1 手ごとにマスの色を変えるので、このグラフは二部グラフです。

• $a,b$ がともに奇数なら、マスの数 $ab$ は奇数です。二部グラフの閉路は偶数長（定理 3.3）なので、閉じた巡回はありません。$3\times3$、$5\times5$ がこれにあたります。
• $4\times4$ にも閉じた巡回はありません。隅のマス a1 から移れるのは b3 と c2 だけで、対角の隅 d4 から移れるのも c2 と b3 だけです。Hamilton 閉路は次数 2 の頂点の辺を両方とも使うので、a1–b3、b3–d4、d4–c2、c2–a1 の 4 辺を含みますが、これは長さ 4 の閉路をなし、長さ 16 の閉路の一部にはなりえません。

$8\times8$ の盤には閉じた巡回があることが知られています。

7. 次数列

定義 7.1（次数列・グラフ的な列）↗

グラフの頂点の次数を大きい順に並べた列を次数列という。非負整数の列 $d_1\ge d_2\ge\cdots\ge d_n$ が、ある（単純）グラフの次数列になっているとき、グラフ的であるという。

握手補題（補題 2.2）から、グラフ的な列の和は偶数です。しかし和が偶数でも、$(3,3,1,1)$ のようにグラフ的でない列があります（次数 3 の 2 頂点はどちらも残りの全頂点と隣接するので、残りの頂点の次数は 2 以上になります）。次の定理は、最大の項を 1 つ取り除く操作で、判定を小さい列に帰着します。

定理 7.2（Havel–Hakimi の定理）✓

$n\ge2$、$d_1\ge d_2\ge\cdots\ge d_n\ge0$ を整数の列とし、$d_1\le n-1$ とする。この列がグラフ的であるためには、長さ $n-1$ の列

$$d'=(d_2-1,\ d_3-1,\ \dots,\ d_{d_1+1}-1,\ d_{d_1+2},\ \dots,\ d_n)$$

（先頭の $d_1$ を取り除き、続く $d_1$ 個の項から 1 ずつ引いたもの）を大きい順に並べ直した列がグラフ的であることが必要十分である。なお $d_1>n-1$ の列はグラフ的でない。

証明（定理 7.2）

$n$ 頂点の単純グラフの次数は $n-1$ 以下なので、最後の主張は定義から従います。

十分性. $d'$ を次数列とするグラフ $G'$ があるとし、その頂点を、$d'$ の並べ直す前の各項に対応させて $v_2,\dots,v_n$ と名付けます。新しい頂点 $v_1$ を足して $v_2,\dots,v_{d_1+1}$ と結ぶと、$v_1$ の次数は $d_1$、$v_2,\dots,v_{d_1+1}$ の次数は 1 ずつ増えて $d_2,\dots,d_{d_1+1}$ になり、残りは変わりません。これは $d$ を次数列とするグラフです。

必要性. 頂点 $v_1,\dots,v_n$ をもち $d(v_i)=d_i$ であるグラフ全体（仮定から空でない有限集合）のうち、$N(v_1)\cap\{v_2,\dots,v_{d_1+1}\}$ の元の個数が最大のもの $G$ を取ります。$N(v_1)=\{v_2,\dots,v_{d_1+1}\}$ であることを示せば、$G-v_1$ の次数列が $d'$ になり、証明が終わります。

そうでないとします。$|N(v_1)|=d_1$ なので、$2\le i\le d_1+1$ で $v_i\notin N(v_1)$ となる $i$ と、$j>d_1+1$ で $v_j\in N(v_1)$ となる $j$ があります。$i<j$ なので $d_i\ge d_j$ です。

$v_i$ と隣接し、$v_j$ と隣接せず、$v_1,v_i,v_j$ のどれとも異なる頂点 $w$ があることを示します。$X=N(v_i)\setminus\{v_j\}$、$Y=N(v_j)\setminus\{v_1,v_i\}$ と置きます。$v_1\in N(v_j)$ に注意すると、

• $v_iv_j\in E(G)$ のとき: $|X|=d_i-1$、$|Y|=d_j-2$。
• $v_iv_j\notin E(G)$ のとき: $|X|=d_i$、$|Y|=d_j-1$。

どちらの場合も $|X|=|Y|+1+(d_i-d_j)>|Y|$ なので、$w\in X\setminus Y$ が取れます。$w\in N(v_i)$ から $w\ne v_i$、$v_1\notin N(v_i)$ から $w\ne v_1$、$w\in X$ から $w\ne v_j$ です。$w\notin Y$ かつ $w\ne v_1,v_i$ なので $w\notin N(v_j)$ です。

$G$ から辺 $v_1v_j$ と $v_iw$ を除き、辺 $v_1v_i$ と $v_jw$ を足したグラフを $G^*$ とします。足した 2 本はもとの $G$ の辺ではなく、互いに異なるので、$G^*$ は単純グラフです。$v_1,v_i,v_j,w$ のそれぞれで辺が 1 本減って 1 本増えるので、すべての頂点の次数は変わりません。$v_1$ の近傍は $v_j$（$j>d_1+1$）が $v_i$（$i\le d_1+1$）に替わったので、$N(v_1)\cap\{v_2,\dots,v_{d_1+1}\}$ の元は 1 つ増えています。これは $G$ の選び方に反します。

∎

例 7.3（次数列 (3,3,2,2,1,1) の判定）

定理 7.2 の操作を繰り返します。

$$(3,3,2,2,1,1)\ \to\ (2,1,1,1,1)\ \to\ (0,0,1,1)=(1,1,0,0)\ \to\ (0,0,0).$$

1 回目は先頭の 3 を除いて続く 3 項から 1 を引き、2 回目は先頭の 2 を除いて続く 2 項から 1 を引いて並べ直し、3 回目は先頭の 1 を除いて次の 1 項から 1 を引きました。$(0,0,0)$ は辺のない 3 頂点のグラフの次数列なので、もとの列はグラフ的です。操作を逆にたどればグラフが作れます。辺のない 3 頂点 $c,e,f$ から始め、頂点 $d$ を足して $c$ と結び（次数 $1,1,0,0$）、頂点 $b$ を足して次数 $0$ の $e,f$ と結び（$2,1,1,1,1$）、最後に頂点 $a$ を足して $b,c,d$ と結びます。辺は $cd,be,bf,ab,ac,ad$ の 6 本で、次数は $a:3,\ b:3,\ c:2,\ d:2,\ e:1,\ f:1$ です。これは木ではありません（$a,c,d$ が三角形をなします）が、連結です。

8. 演習

演習 8.1易

$n\ge2$ 頂点の（単純）グラフには、次数の等しい 2 頂点があることを示せ。

解答

次数は $0,1,\dots,n-1$ の $n$ 通りの値を取りえます。しかし、次数 $0$ の頂点（どの頂点とも隣接しない）と次数 $n-1$ の頂点（他の全頂点と隣接する）は同時には存在しません。したがって、実際に現れる次数の値は $\{0,\dots,n-2\}$ か $\{1,\dots,n-1\}$ のどちらかに含まれ、高々 $n-1$ 通りです。$n$ 個の頂点に高々 $n-1$ 通りの値を割り当てるので、鳩の巣原理（定理 7.5［数え上げと母関数］）から、次数の等しい 2 頂点があります。

演習 8.2標準

列 $(4,4,3,2,2,1)$ と $(5,4,3,2,1,1)$ がグラフ的かどうかを判定せよ。

解答

$(4,4,3,2,2,1)\to(3,2,1,1,1)\to(1,0,0,1)=(1,1,0,0)\to(0,0,0)$ で、最後の列はグラフ的なので、定理 7.2 からもとの列もグラフ的です。

$(5,4,3,2,1,1)\to(3,2,1,0,0)\to(1,0,-1,0)$ となり、負の項が現れます。負の項をもつ列はグラフ的でないので、$(3,2,1,0,0)$ も $(5,4,3,2,1,1)$ もグラフ的ではありません。直接の理由もあります。6 頂点で次数 5 の頂点は他の全頂点と隣接するので、それを除いた 5 頂点の次数は $3,2,1,0,0$ です。次数 3 の頂点は自分以外の 4 頂点のうち 3 つと隣接する必要がありますが、次数 0 の頂点が 2 つあるので、隣接できる相手は 2 つしかありません。

演習 8.3標準

最大次数が $k\ge1$ の木には、葉（次数 1 の頂点）が $k$ 個以上あることを示せ。

解答

木の頂点数を $n$、葉の個数を $\ell$ とし、次数 $k$ の頂点 $x$ を 1 つ固定します。$k=1$ なら $x$ 自身が葉です。$k\ge2$ とします。葉でも $x$ でもない $n-\ell-1$ 個の頂点の次数は 2 以上なので（$n\ge2$ の木は連結だから次数 0 の頂点はありません）、握手補題（補題 2.2）と辺数 $n-1$（定理 4.4 の 5）から

$$2(n-1)=\sum_v d(v)\ge \ell+k+2(n-\ell-1)=2n-2+k-\ell$$

です。整理すると $\ell\ge k$ です。

演習 8.4難

$n\ge3$ 頂点のグラフ $G$ の辺の数が $\binom{n-1}{2}+2$ 以上ならば、$G$ は Hamilton 閉路をもつことを示せ。また、辺の数が $\binom{n-1}{2}+1$ で Hamilton 閉路をもたないグラフを挙げよ。

解答

Ore の定理（定理 6.5）の仮定を確かめます。$u,v$ を隣接しない 2 頂点とします。$u$ にも $v$ にも接続しない辺は $G-\{u,v\}$ の辺で、その数は $\binom{n-2}{2}$ 以下です。$u$ と $v$ は隣接しないので、残りの辺は $u$ か $v$ のちょうど一方に接続し、その数は $d(u)+d(v)$ です。よって

$$d(u)+d(v)\ge\binom{n-1}{2}+2-\binom{n-2}{2}=(n-2)+2=n$$

です。ここで $\binom{n-1}{2}-\binom{n-2}{2}=n-2$ を使いました。Ore の定理から $G$ は Hamilton 閉路をもちます。

$K_{n-1}$ に新しい頂点を 1 つ足し、$K_{n-1}$ の 1 頂点とだけ結んだグラフは、辺の数が $\binom{n-1}{2}+1$ です。新しい頂点の次数は 1 で、Hamilton 閉路は各頂点で 2 本の辺を使うので、このグラフは Hamilton 閉路をもちません。したがって辺数の条件はこれ以上弱められません。

参考文献

• R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer — 第 1 章（基本概念）、第 10 章（Hamilton 閉路）。
• J. A. Bondy, U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008 — 木、Euler 回路、Hamilton 閉路の章。
• D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001 — 第 1 章（次数列、Havel–Hakimi）、第 7 章（Hamilton 閉路）。
• G. A. Dirac, “Some theorems on abstract graphs”, Proc. London Math. Soc. (3) 2 (1952), 69–81.
• J. A. Bondy, V. Chvátal, “A method in graph theory”, Discrete Math. 15 (1976), 111–135.