Euler閉路
概要
Euler閉路（Eulerian circuit）とは、グラフのすべての辺をちょうど 1 回ずつ通って出発点に戻る閉じた道筋（閉小道）のことである。頂点は何度通ってもよい。Euler の定理により、辺をもつ有限な多重グラフが Euler 閉路をもつための必要十分条件は、すべての頂点の次数が偶数で、辺がすべて 1 つの連結成分に収まることである。出発点に戻らなくてよい一筆書き（Euler 路）は、同じ連結性の条件のもとで、次数が奇数の頂点が 0 個か 2 個のときに限って存在する。Königsberg の 7 つの橋では 4 つの陸地の次数が 5, 3, 3, 3 とすべて奇数なので、どの橋も 1 回ずつ渡る散歩はできない。すべての頂点を 1 回ずつ通る Hamilton 閉路とは別の概念である。
前提知識: グラフ, 多重グラフ, 次数(グラフ), 連結グラフ
18 世紀の Königsberg（現在のロシアのカリーニングラード）では、Pregel 川の 2 つの中州と両岸が 7 本の橋で結ばれていた。「どの橋もちょうど 1 回ずつ渡って、出発点に戻る散歩はできるか」という問いに、Euler は否と答えた。陸地を頂点、橋を辺とみなすと、各陸地に架かる橋の本数（頂点の次数）は中州の一方が $5$、残りの 3 つが $3$ で、すべて奇数である。散歩の途中で陸地に入ったら必ず出るので、通過のたびに橋を 2 本ずつ使う。したがって出発点でも途中の点でも、架かる橋の本数は偶数でなければならず、この散歩は不可能である。このように、グラフのすべての辺をちょうど 1 回ずつ通って出発点に戻る閉じた道筋を Euler 閉路 という。本記事の主定理は、辺をもつ有限グラフが Euler 閉路をもつための必要十分条件は「すべての頂点の次数が偶数で、辺がすべて 1 つの連結成分に入っている」ことだ、というものである。条件を少し変えると、出発点に戻らなくてよい「一筆書き」ができる条件も得られる。
定義
本記事では、グラフ の記事の流儀に従い、有限な多重グラフ $G=(V,E,\partial)$ を扱う。$V$ と $E$ は有限集合で、写像 $\partial$ は各辺 $e$ にその端点の対 $\partial(e)=\{u,v\}$（$u\neq v$）を対応させる。同じ頂点対を結ぶ辺（平行辺）が何本あってもよいが、両端が同じ頂点であるループは許さない（ループについては rem-eulerian-circuit-loops で扱う）。単純グラフは平行辺をもたない多重グラフとみなす。頂点 $v$ の次数 $\deg(v)$ は $v$ を端点にもつ辺の本数である（次数(グラフ)）。
多重グラフ $G=(V,E,\partial)$ の歩道（walk）とは、頂点と辺を交互に並べた列
$$
W=(v_0,e_1,v_1,e_2,\dots,e_\ell,v_\ell)\qquad(\ell\geq0)
$$
であって、各 $i=1,\dots,\ell$ について $\partial(e_i)=\{v_{i-1},v_i\}$ となるものをいう。$\ell$ を $W$ の長さ、$v_0$ を始点、$v_\ell$ を終点という。辺 $e_1,\dots,e_\ell$ が相異なる歩道を小道（trail）といい、$v_0=v_\ell$ である小道を閉小道（closed trail, circuit）という。
多重グラフ $G=(V,E,\partial)$ の小道 $W=(v_0,e_1,v_1,\dots,e_\ell,v_\ell)$ が $G$ のすべての辺をちょうど 1 回ずつ通るとき、すなわち $\{e_1,\dots,e_\ell\}=E$ かつ $\ell=|E|$ であるとき、$W$ を Euler 路（Euler trail, 一筆書き）という。Euler 路のうち閉小道であるもの（$v_0=v_\ell$）を Euler 閉路（Eulerian circuit）という。Euler 閉路をもつグラフを Euler グラフ（Eulerian graph）という。
Euler 路は出発点に戻らなくてもよい一筆書きであり、Euler 閉路は出発点に戻る一筆書きである。辺をもたないグラフ（$E=\emptyset$）では、1 頂点だけからなる長さ $0$ の歩道が形式的に Euler 閉路になるが、以下の定理では $E\neq\emptyset$ を仮定して、この退化した場合を除く。
グラフ の記事では、始点以外の頂点が相異なる長さ $3$ 以上の閉歩道を閉路（cycle）とよび、辺が相異なるだけの閉歩道を閉小道（circuit）とよんで区別している。Euler 閉路は同じ頂点を何度通ってもよいので、この用語法では閉路ではなく閉小道である。「Euler 閉路」は英語の Eulerian circuit（Euler tour ともいう）の定着した訳語であり、「Euler 回路」ともよばれる。すべての頂点をちょうど 1 回ずつ通る閉路は Hamilton閉路 といい、Euler 閉路とは別の概念である（rem-eulerian-circuit-hamilton）。
Euler 閉路は辺をすべて通るので、次数 $0$ の頂点（孤立点）は Euler 閉路に現れない。孤立点を加えても除いても Euler 閉路の有無は変わらないので、連結性の条件は「辺をもつ頂点がすべて同じ連結成分（連結成分(グラフ)）に属する」という形で述べるのが正確である。この条件を以下では「辺が 1 つの連結成分に収まる」と言い表す。$G$ が連結グラフなら、この条件は満たされる。
例と反例
中州の一方（Kneiphof 島）を $A$、北岸を $B$、南岸を $C$、もう一方の中州を $D$ とする。橋は $A$ と $B$ の間に 2 本、$A$ と $C$ の間に 2 本、$A$ と $D$、$B$ と $D$、$C$ と $D$ の間に 1 本ずつあり、計 7 本である。これは平行辺をもつ多重グラフで、次数は
$$
\deg(A)=5,\quad \deg(B)=3,\quad \deg(C)=3,\quad \deg(D)=3
$$
である。すべて奇数なので、thm-eulerian-circuit-euler により Euler 閉路は存在しない。奇数次数の頂点が $4$ 個あるので、cor-eulerian-circuit-trail により出発点に戻らない一筆書き（Euler 路）も存在しない。この問題の解決はグラフ理論の出発点とされる（KT17 §5.3、Lev §2.4）。
5 頂点の完全グラフ $K_5$ では、すべての頂点の次数が $4$ である。頂点を $1,2,3,4,5$ とすると、頂点の列
$$
1,\ 2,\ 3,\ 4,\ 5,\ 1,\ 3,\ 5,\ 2,\ 4,\ 1
$$
は $10$ 本の辺 $12,23,34,45,51,13,35,52,24,41$ を 1 回ずつ通る。$K_5$ の辺はちょうど $\binom{5}{2}=10$ 本なので、これは Euler 閉路である。一般に $n\geq3$ のとき $K_n$ の各頂点の次数は $n-1$ なので、$K_n$ が Euler 閉路をもつことと $n$ が奇数であることは同値である（thm-eulerian-circuit-euler）。
正方形 $abcd$（辺 $ab,bc,cd,da$）に 2 本の対角線 $ac,bd$ を引き、上に屋根の頂点 $e$ を置いて辺 $ce,de$ を加えた 5 頂点 8 辺のグラフを考える（$a,b$ が底辺の両端、$c,d$ が上の角）。次数は
$$
\deg(a)=3,\quad\deg(b)=3,\quad\deg(c)=4,\quad\deg(d)=4,\quad\deg(e)=2
$$
である。奇数次数の頂点は $a,b$ の 2 個なので Euler 閉路はないが、$a$ から $b$ への Euler 路がある。たとえば
$$
a,\ b,\ c,\ d,\ a,\ c,\ e,\ d,\ b
$$
は 8 本の辺 $ab,bc,cd,da,ac,ce,ed,db$ を 1 回ずつ通る。cor-eulerian-circuit-trail によれば、どの Euler 路も $a$ と $b$ を両端にもつ。
互いに辺で結ばれていない 2 つの三角形（頂点 $1,2,3$ と $4,5,6$、辺 $12,23,31,45,56,64$）からなるグラフでは、すべての頂点の次数が $2$ で偶数である。しかし小道は 1 つの連結成分の中にとどまるので、両方の三角形の辺をすべて通る小道はなく、Euler 閉路は存在しない。満たす性質は「すべての頂点の次数が偶数」、満たさない性質は「辺が 1 つの連結成分に収まる」であり、破る含意は「すべての頂点の次数が偶数ならば Euler 閉路がある」である。次数の条件だけでは足りず、連結性の条件が必要であることをこの例は示している。
完全グラフ $K_4$ は連結で、すべての頂点の次数が $3$ である。奇数次数の頂点が $4$ 個あるので、$K_4$ には Euler 閉路も Euler 路もない。満たす性質は「連結」、満たさない性質は「すべての頂点の次数が偶数」である。星グラフ $K_{1,3}$（中心と 3 枚の葉）も同じく奇数次数の頂点を $4$ 個もち、一筆書きできない。
定理と証明
証明では、小道が頂点を通るたびに辺を何本使うかを数える。次の補題はその数え方を正確にしたものである。
$W=(v_0,e_1,v_1,\dots,e_\ell,v_\ell)$ を多重グラフ $G$ の小道（$\ell\geq1$）とし、$v$ を頂点とする。$W$ の辺のうち $v$ を端点にもつものの本数を $c_W(v)$ と書き、$m(v)$ を $1\leq j\leq\ell-1$ かつ $v_j=v$ となる添字 $j$ の個数とする。このとき
$$
c_W(v)=2m(v)+[v=v_0]+[v=v_\ell]
$$
が成り立つ。ここで $[P]$ は条件 $P$ が成り立てば $1$、成り立たなければ $0$ を表す。特に、$W$ が閉小道なら $c_W(v)$ はすべての頂点で偶数であり、$v_0\neq v_\ell$ なら $c_W(v)$ が奇数である頂点はちょうど $v_0$ と $v_\ell$ の 2 個である。
辺 $e_i$ の端点は $v_{i-1}$ と $v_i$ であり、ループを許さないので $v_{i-1}\neq v_i$ である。したがって $e_i$ が $v$ を端点にもつことは、「$v_{i-1}=v$」と「$v_i=v$」のちょうど一方が成り立つことと同値である。小道なので $e_1,\dots,e_\ell$ は相異なり、
$$
c_W(v)=\bigl|\{i\mid v_{i-1}=v\}\bigr|+\bigl|\{i\mid v_i=v\}\bigr|
$$
となる。右辺の第 1 項は $0\leq j\leq\ell-1$ で $v_j=v$ となる $j$ の個数、第 2 項は $1\leq j\leq\ell$ で $v_j=v$ となる $j$ の個数である。両者で $1\leq j\leq\ell-1$ の部分はともに $m(v)$ で、残りは第 1 項の $j=0$ と第 2 項の $j=\ell$ だから、主張の式が得られる。閉小道なら $v_0=v_\ell$ なので $[v=v_0]+[v=v_\ell]$ は $0$ か $2$ であり、$c_W(v)$ は偶数である。$v_0\neq v_\ell$ なら $[v=v_0]+[v=v_\ell]$ が $1$ になるのは $v=v_0$ と $v=v_\ell$ のときだけである。$\square$
Euler 路 $W$ はすべての辺を 1 回ずつ通るので、$c_W(v)=\deg(v)$ である。これが次の定理の必要性の核心である。
$G$ を辺を少なくとも 1 本もつ有限な多重グラフとする。$G$ が Euler 閉路をもつための必要十分条件は、次の 2 条件がともに成り立つことである。
- $G$ のすべての頂点の次数が偶数である。
- $G$ の辺が 1 つの連結成分に収まる（辺をもつ頂点がすべて同じ連結成分に属する）。
特に、辺をもつ連結な多重グラフが Euler 閉路をもつことと、すべての頂点の次数が偶数であることは同値である。
必要性。$W=(v_0,e_1,\dots,e_\ell,v_\ell)$ を Euler 閉路とする。$W$ はすべての辺を 1 回ずつ通るので、各頂点 $v$ で $\deg(v)=c_W(v)$ であり、lem-eulerian-circuit-count によりこれは偶数である。また、$x,y$ を辺をもつ頂点とすると、$x$ も $y$ も $W$ のある辺の端点なので $W$ の上に現れる。$x=v_i$、$y=v_j$（$i\leq j$）とすると、$W$ の一部 $(v_i,e_{i+1},\dots,e_j,v_j)$ は $x$ と $y$ を結ぶ歩道であり、グラフ の記事の命題「連結成分への分解」と同じ議論により $x$ と $y$ は同じ連結成分に属する。よって条件 2 も成り立つ。
十分性。条件 1 と 2 を仮定する。$G$ の小道の長さは $|E|$ 以下なので、長さが最大の小道 $W=(v_0,e_1,v_1,\dots,e_\ell,v_\ell)$ がとれる。$E\neq\emptyset$ だから長さ $1$ の小道があり、$\ell\geq1$ である。
(a) $W$ は閉小道である。$v_0\neq v_\ell$ と仮定すると、lem-eulerian-circuit-count により $c_W(v_\ell)$ は奇数である。$\deg(v_\ell)$ は偶数なので $c_W(v_\ell)<\deg(v_\ell)$ であり、$v_\ell$ を端点にもつ辺 $f$ で $W$ が使っていないものがある。$\partial(f)=\{v_\ell,u\}$ とすると $(v_0,e_1,\dots,e_\ell,v_\ell,f,u)$ は長さ $\ell+1$ の小道であり、$W$ の最大性に反する。よって $v_0=v_\ell$ である。
(b) $W$ はすべての辺を通る。$W$ が使わない辺 $f$ があると仮定し、その端点の一方を $x$ とする。$x$ と $v_0$ はどちらも辺をもつ頂点なので、条件 2 により $v_0=u_0,g_1,u_1,\dots,g_k,u_k=x$ という歩道がある。$u_k=x$ は未使用の辺 $f$ を端点にもつので、「$u_j$ が $W$ の使わない辺を端点にもつ」ような最小の $j$ がとれる。$j=0$ なら $u_0=v_0$ は $W$ の上の頂点である。$j\geq1$ なら $u_{j-1}$ は未使用の辺を端点にもたないので、$u_{j-1}$ を端点にもつ辺 $g_j$ は $W$ で使われており、その端点 $u_j$ は $W$ の上に現れる。いずれの場合も、$W$ の上の頂点 $w=v_i$ で、$W$ が使わない辺 $g$ を端点にもつものがある。$W$ は閉小道なので、始点を $v_i$ にずらした
$$
W'=(v_i,e_{i+1},\dots,e_\ell,v_\ell=v_0,e_1,\dots,e_i,v_i)
$$
も同じ辺を 1 回ずつ使う閉小道である。$\partial(g)=\{w,u\}$ として $W'$ の末尾に $g,u$ を付け加えると長さ $\ell+1$ の小道が得られ、$W$ の最大性に反する。よって $W$ はすべての辺を通る。
(a) と (b) により $W$ は Euler 閉路である。最後の主張は、連結なグラフでは条件 2 が自動的に成り立つことから従う。$\square$
条件 2 を「$G$ が連結」に置き換えた形は KT17 §5.3 の Theorem 5.13（p. 77）であり、そこでは単純グラフで述べたうえで、同じ定理がループのない多重グラフでも成り立つと注意している（p. 78）。上の証明は存在を示すだけだが、KT17 の証明は、閉小道に未使用の辺からなる閉小道を継ぎ足していく手続きとして書かれており、そのまま Euler 閉路を求める算法になる（rem-eulerian-circuit-algorithm）。
$G$ を辺を少なくとも 1 本もち、辺が 1 つの連結成分に収まる有限な多重グラフとする。
- 相異なる頂点 $a,b$ について、$G$ が $a$ を始点、$b$ を終点とする Euler 路をもつための必要十分条件は、次数が奇数の頂点がちょうど $a$ と $b$ の 2 個であることである。
- $G$ が Euler 路（閉じていてもいなくてもよい）をもつための必要十分条件は、次数が奇数の頂点の個数が $0$ または $2$ であることである。
1 の必要性：$a$ から $b$ への Euler 路 $W$ では各頂点で $\deg(v)=c_W(v)$ であり、lem-eulerian-circuit-count により $c_W(v)$ が奇数である頂点はちょうど $a$ と $b$ である。
1 の十分性：$G$ に $a$ と $b$ を結ぶ新しい辺 $f^{*}$ を 1 本加えた多重グラフを $G^{+}$ とする（$a$ と $b$ の間に既に辺があれば、$f^{*}$ はそれと平行な辺になる）。$G^{+}$ では $a$ と $b$ の次数が $1$ ずつ増えて偶数になり、他の頂点の次数は変わらないので、すべての頂点の次数が偶数である。$a,b$ はともに奇数次数なので辺をもち、辺が 1 つの連結成分に収まるという性質は $G^{+}$ でも保たれる。thm-eulerian-circuit-euler により $G^{+}$ は Euler 閉路 $(v_0,e_1,\dots,e_\ell,v_\ell)$ をもつ。$f^{*}=e_i$ とし、thm-eulerian-circuit-euler の証明の (b) と同じように始点を $v_i$ にずらすと、$f^{*}$ が最後の辺になる閉小道が得られる。その最後の辺 $f^{*}$ と終点を取り除いた部分は $G$ の辺をすべて 1 回ずつ通る小道で、両端は $a$ と $b$ である。必要なら向きを逆にたどれば、$a$ から $b$ への Euler 路が得られる。
2：奇数次数の頂点が $0$ 個なら thm-eulerian-circuit-euler により Euler 閉路があり、これは Euler 路である。ちょうど $2$ 個なら 1 により Euler 路がある。逆に Euler 路 $W$ があれば、lem-eulerian-circuit-count により奇数次数の頂点は、$W$ が閉じていれば $0$ 個、閉じていなければ $2$ 個である。$\square$
次数(グラフ) の記事の系「次数が奇数の頂点の個数」（次数(グラフ) の定理「次数の総和と辺数」の帰結）により、奇数次数の頂点の個数は常に偶数である。したがって 2 の条件は「奇数次数の頂点が $2$ 個以下」と言っても同じであり、Lev §2.4.2（p. 144）はこの形で述べている。ただし Lev はこの節のグラフが連結であることを前提としており、十分性は考え方を述べるだけで、証明は与えていない。
有限な多重グラフ $G$ のすべての頂点の次数が偶数ならば、$G$ の辺集合は、辺を共有しない有限個の閉小道の辺集合の和に分割できる（$E=\emptyset$ なら 0 個）。
辺をもつ連結成分を $G_1,\dots,G_r$ とする。各 $G_k$ は辺をもつ連結な多重グラフで、次数は $G$ での次数と同じだから偶数である。thm-eulerian-circuit-euler により $G_k$ は Euler 閉路 $W_k$ をもち、$W_1,\dots,W_r$ の辺集合は $E$ を分割する。$\square$
有向グラフの場合
一方通行の道路網のように辺に向きがある場合も、同じ考え方で Euler 閉路の条件が得られる。グラフ の記事の多重有向グラフ $D=(V,E,i,t)$ では、各辺 $e$ に始点 $i(e)$ と終点 $t(e)$ が定まる（$i(e)=t(e)$ となるループも許す）。頂点 $v$ の出次数 $\deg^{+}(v)$ は $i(e)=v$ となる辺の本数、入次数 $\deg^{-}(v)$ は $t(e)=v$ となる辺の本数である（次数(グラフ)）。有向の小道 $(v_0,e_1,v_1,\dots,e_\ell,v_\ell)$ とは、各 $e_j$ が $i(e_j)=v_{j-1}$、$t(e_j)=v_j$ を満たし、$e_1,\dots,e_\ell$ が相異なるものをいい、すべての辺をちょうど 1 回ずつ通る閉じた有向の小道を有向 Euler 閉路という。
$D$ を辺を少なくとも 1 本もつ有限な多重有向グラフとし、向きを無視した多重グラフで $D$ の辺が 1 つの連結成分に収まるとする。$D$ が有向 Euler 閉路をもつための必要十分条件は、すべての頂点 $v$ で $\deg^{+}(v)=\deg^{-}(v)$ となることである。
有向の小道 $W=(v_0,e_1,\dots,e_\ell,v_\ell)$ が頂点 $v$ で使う辺のうち、$v$ から出るものの本数を $c^{+}_W(v)$、$v$ に入るものの本数を $c^{-}_W(v)$ とする。$v_j=v$ となる添字 $j$ ごとに、$j\leq\ell-1$ なら出る辺 $e_{j+1}$ を、$j\geq1$ なら入る辺 $e_j$ を 1 本ずつ数えればよい（ループ $e_{j+1}$ は $j$ で出る辺として、$j+1$ で入る辺として 1 回ずつ数えられる）。したがって
$$
c^{+}_W(v)-c^{-}_W(v)=[v=v_0]-[v=v_\ell]
$$
である。
必要性：有向 Euler 閉路 $W$ では $v_0=v_\ell$ なので右辺は $0$ であり、すべての辺を 1 回ずつ使うので $\deg^{+}(v)=c^{+}_W(v)=c^{-}_W(v)=\deg^{-}(v)$ である。
十分性：長さ最大の有向の小道 $W$ をとる。$v_0\neq v_\ell$ なら $c^{-}_W(v_\ell)=c^{+}_W(v_\ell)+1$ であり、$\deg^{+}(v_\ell)=\deg^{-}(v_\ell)\geq c^{-}_W(v_\ell)>c^{+}_W(v_\ell)$ だから、$v_\ell$ から出る未使用の辺があって $W$ を延ばせる。これは最大性に反するので $W$ は閉じている。次に、未使用の辺があると仮定すると、thm-eulerian-circuit-euler の証明の (b) と同じ議論（向きを無視した歩道を使う）により、$W$ の上の頂点 $w$ で未使用の辺を端点にもつものがある。$W$ は閉じているので $c^{+}_W(w)=c^{-}_W(w)$ であり、$\deg^{+}(w)=\deg^{-}(w)$ とあわせると、$w$ から出る未使用の辺の本数と $w$ に入る未使用の辺の本数は等しく、その和は $1$ 以上だから、$w$ から出る未使用の辺 $g$ がある。始点を $w$ にずらした $W$ の末尾に $g$ を付け加えると、より長い有向の小道が得られて矛盾する。よって $W$ は有向 Euler 閉路である。$\square$
補足
ループ（両端が同じ頂点 $v$ の辺）を許す多重グラフでは、次数(グラフ) の記事の約束に従ってループを $v$ の次数に $2$ と数える。この約束のもとで thm-eulerian-circuit-euler と cor-eulerian-circuit-trail はそのまま成り立つ。実際、ループ $e_i$ では $v_{i-1}=v_i=v$ であり、lem-eulerian-circuit-count の証明の式の右辺の 2 つの項で $e_i$ が 1 回ずつ数えられるので、$c_W(v)$ を「$W$ の辺の端点としての $v$ の重複度の和」と読めば同じ式が成り立ち、残りの議論は変わらない。つまり、ループを含み辺を少なくとも 1 本もつ有限な多重グラフが Euler 閉路をもつための必要十分条件は、すべての頂点の次数が偶数であり（ループは次数に $2$ と数える）、辺（ループを含む）をもつ頂点がすべて 1 つの連結成分に属することである。ループは異なる頂点どうしをつながないので、連結成分はループでない辺だけで決まる。したがって、ループ以外の辺をもたない頂点にループが付いていると、その頂点はほかの頂点とつながらず単独の連結成分をなし、ほかの頂点も辺をもてば連結性の条件が破れる。たとえば、三角形 $\{1,2,3\}$ に、辺を共有しない頂点 $4$ とそこでのループを加えたグラフでは、次数はすべて $2$ で偶数だが、辺をもつ頂点 $1,2,3,4$ が 2 つの連結成分 $\{1,2,3\}$ と $\{4\}$ に分かれるので、Euler 閉路は存在しない。ループを除けば三角形が Euler 閉路をもつので、この例ではループの有無で Euler 閉路の有無が変わる（頂点 $4$ にループを 2 本付けても同じである）。一方、どのループの端点もループでない辺をもつなら、ループを除いても次数の偶奇は変わらず、辺をもつ頂点の集合と連結成分も変わらないので、ループを除いたグラフと Euler 閉路の有無は変わらない。実際、ループはそれ自体で長さ $1$ の閉小道であり、ループを除いたグラフの Euler 閉路がその端点を通る時点で途中に挿入できる。
KT17 §5.3 の Theorem 5.13 の証明（p. 77）は、次の手続きで Euler 閉路を実際に作る。まず 1 頂点だけの閉小道から始める。現在の閉小道 $C$ の上に、未使用の辺を端点にもつ頂点 $u_0$ があれば、$u_0$ から未使用の辺だけをたどって進めなくなるまで歩く。すべての次数が偶数なら、この歩みは $u_0$ に戻って止まる（止まった頂点が $u_0$ と異なれば、lem-eulerian-circuit-count によりそこで使った辺の本数が奇数になり、次数が偶数であることに反する）。こうして得た閉小道を $C$ の $u_0$ の位置に継ぎ足す。未使用の辺が無くなるまで繰り返すと Euler 閉路が得られる。KT17 p. 78 には 11 頂点のグラフでの実行例がある。この手続きは Hierholzer の名で呼ばれることが多い。
Euler 閉路はすべての辺をちょうど 1 回ずつ通る閉じた道筋であり、Hamilton閉路 はすべての頂点をちょうど 1 回ずつ通る閉路である。Euler 閉路の有無は thm-eulerian-circuit-euler により次数と連結性を調べるだけで判定できるが、Hamilton 閉路（や Hamilton 道）の有無についてはそのような簡単な判定法が知られておらず、一般のグラフでこれを判定する問題は NP完全 である（Lev §2.4.3、pp. 144–145）。たとえば Königsberg の橋のグラフ（ex-eulerian-circuit-konigsberg）には Euler 路はないが、4 つの陸地を 1 回ずつ訪れる道筋はある。
Königsberg の橋の問題は Euler の論文 Eul41 で解かれた。KT17 §5.3（p. 75）は Euler がこの問題を 1736 年に解決したとし、Lev §2.1（p. 100）はグラフ理論が 1735 年に Euler によって初めて研究されたとする。論文はペテルブルク科学アカデミー紀要の 1736 年の巻に載ったが、その巻の刊行は 1741 年であり、文献によって挙げる年が異なる。Euler はこの論文で、奇数次数の頂点が 3 個以上あれば一筆書きができないことを示し、条件が満たされれば一筆書きができることを述べたが、十分性の証明は与えなかった。十分性の最初の証明は Hierholzer による（Hie73、死後の刊行）。
同じく Euler の名がつく Eulerの公式(平面グラフ)（連結な平面グラフの頂点数・辺数・面数の関係）は別の定理であり、その証明は 平面グラフ の記事にある。
関連項目
- 前提: グラフ, 多重グラフ, 次数(グラフ), 連結グラフ
- 比較: Hamilton閉路, 有向グラフ
- 例: 完全グラフ
- 区別: Eulerの公式(平面グラフ)
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
