閉路

同義語：cycle (graph theory)

概要

前提知識: グラフ, 部分グラフ, 連結グラフ

グラフの辺をたどって出発点に戻る経路には、同じ辺を往復するだけのものや、途中で同じ頂点を何度も通るものもある。そのうち、出発点以外の頂点を 2 度通らずに一周するものを閉路という。閉路は「輪」を取り出した概念であり、グラフの構造の基本的な分かれ目になる。閉路をもたない連結グラフが木であり、長さが奇数の閉路をもたないことが二部グラフを特徴づける。閉路の辺は 1 本除いても連結性を壊さない（橋ではない）。辺の集合を $2$ を法とするベクトルとみると、閉路は「どの頂点の次数も偶数の辺集合」のなす空間（閉路空間）を生成し、その次元は $\lvert E\rvert-\lvert V\rvert+c$ である（$c$ は連結成分の個数）。最短の閉路の長さ（内周）は、頂点の個数の下界を与える。

定義

この記事の「グラフ」は、グラフの記事の定義「グラフの定義」の単純無向グラフ $G=(V,E)$ である。特に断らない限り有限グラフを考える。歩道・閉歩道・小道・閉小道はグラフの記事の定義「歩道・道・閉路の定義」のとおりである。

閉路・内周・森

$G=(V,E)$ をグラフとする。

$G$ の閉路（cycle）とは、閉歩道 $v_0,v_1,\dots,v_{\ell-1},v_0$ であって、$\ell\ge3$ かつ $v_0,\dots,v_{\ell-1}$ が相異なるものをいう。$\ell$ を閉路の長さという。長さが奇数の閉路を奇閉路、偶数の閉路を偶閉路という。
閉路 $v_0,\dots,v_{\ell-1},v_0$ に対し、頂点 $v_0,\dots,v_{\ell-1}$ と辺 $v_0v_1,\ v_1v_2,\ \dots,\ v_{\ell-2}v_{\ell-1},\ v_{\ell-1}v_0$ からなる部分グラフを、その閉路が定める部分グラフという。
閉路をもたないグラフを森（forest）、連結な森を木（tree）という。
閉路をもつグラフ $G$ の閉路の長さの最小値を $G$ の内周（girth）といい、$g(G)$ と書く。森の内周は $\infty$ とする。

1 はグラフの記事の定義「歩道・道・閉路の定義」の閉路と同じである。条件 $\ell\ge3$ は、辺 $uv$ を往復するだけの長さ $2$ の閉歩道 $u,v,u$ を閉路から除くためのものである（グラフの記事の例「反例：長さ 2 の閉歩道」）。単純グラフにはループがないので長さ $1$ の閉歩道はなく、閉路の長さはつねに $3$ 以上である。閉路の $\ell$ 本の辺 $v_{i-1}v_i$ は相異なる（端点の対が相異なるので）から、閉路は閉小道でもある。KT17 §5.1（pdf p. 95）も、相異なる $n\ge3$ 頂点の道 $x_1,\dots,x_n$ で $x_1x_n$ も辺であるものを閉路（cycle）とし、長さを辺の本数としている。3 の木の定義は木の記事の定義と同じである。
閉路の定める部分グラフは、閉路グラフ $C_\ell$（グラフの記事の例「道グラフと閉路グラフ」）と同型である。同じ部分グラフを定める閉路は、出発点の選び方（$\ell$ 通り）と回る向き（$2$ 通り）だけ異なり、ちょうど $2\ell$ 個ある。閉路の個数を数えるときは、ふつう定める部分グラフが同じものを同一視する。以下でも「$G$ の閉路」を、それが定める部分グラフと同一視することがある。部分グラフの閉路は元のグラフの閉路であり、森の部分グラフは森である（部分グラフの記事の命題「道・閉路・二部性の保存」）。
「閉路グラフ $C_n$」はグラフの名前であり、「$G$ の閉路」は $G$ の中の経路（またはその定める部分グラフ）である。次の命題は、どのようなグラフが閉路グラフと同型になるかを次数で特徴づける。

連結で次数がすべて 2 のグラフ

頂点を 1 個以上もつ有限グラフ $H$ について、次は同値である。

ある $\ell\ge3$ について $H$ は閉路グラフ $C_\ell$ と同型である。
$H$ は連結で、すべての頂点の次数が $2$ である。
したがって、有限グラフですべての頂点の次数が $2$ のものは、閉路グラフの非交和である。

1 ⇒ 2 は $C_\ell$ についてのグラフの記事の例「道グラフと閉路グラフ」による。
2 ⇒ 1：頂点 $v_0$ と、その隣接頂点 $v_1$ をとる。$v_0,\dots,v_i$（$i\ge1$）まで決めたら、$v_i$ の 2 つの隣接頂点のうち $v_{i-1}$ でない方を $v_{i+1}$ とする。$H$ は有限なので、$v_j\in\{v_0,\dots,v_{j-1}\}$ となる最小の $j$ がある。$v_j=v_k$（$0\le k\le j-1$）とする。$v_j$ は $v_{j-1}$ の隣接頂点なので $k\neq j-1$、作り方から $v_j\neq v_{j-2}$ なので $k\neq j-2$ である。$k\ge1$ とすると、$v_k$ は相異なる 3 頂点 $v_{k-1},v_{k+1},v_{j-1}$（添字が相異なり、$j$ の最小性からこれらの頂点は相異なる）と隣接し、次数 $2$ に反する。よって $k=0$ で、$j\ge3$ であり、$Z:\ v_0,v_1,\dots,v_{j-1},v_0$ は $H$ の閉路である。
$Z$ の各頂点は $Z$ の中で 2 頂点と隣接し（$v_0$ は $v_1$ と $v_{j-1}$）、次数が $2$ なので、$Z$ の頂点に接続する $H$ の辺はすべて $Z$ の辺である。よって $Z$ の頂点集合 $S$ について $E(S,V(H)\setminus S)=\emptyset$ であり、連結グラフの記事の命題「切断による判定」から $S=V(H)$ である。$H$ のすべての辺は $Z$ の $j$ 本の辺なので、$H$ は $C_j$ と同型である。最後の主張は、各連結成分にこの同値を使えばよい。$\square$

例

完全グラフの閉路の個数

$K_n$ の長さ $\ell$（$3\le\ell\le n$）の閉路の個数（定める部分グラフで数える）は
$$ \binom{n}{\ell}\cdot\frac{(\ell-1)!}{2} $$
である。$\ell$ 個の頂点を選ぶと、それらを一周する順序は、出発点を固定した並べ方 $(\ell-1)!$ 通りを向きの $2$ 通りで割った数だけあり、$K_n$ ではどの並べ方も閉路になるからである。$K_4$ では三角形が $4\cdot1=4$ 個、長さ $4$ の閉路が $1\cdot3=3$ 個で、合わせて $7$ 個ある。

Petersen グラフの例

$\{1,2,3,4,5\}$ の 2 元部分集合 $10$ 個を頂点とし、交わらない 2 つを辺で結んだグラフを Petersen グラフという。各頂点 $\{a,b\}$ は残り 3 元から作る 2 元部分集合 3 個と隣接するので、すべての頂点の次数は $3$ で、辺は $15$ 本である。頂点 $\{a,b\}$ を $ab$ と書く。

三角形はない。互いに交わらない 2 元部分集合 3 個には $6$ 個の元が要るからである。
長さ $4$ の閉路はない。長さ $4$ の閉路 $u,x,w,y,u$ があれば、三角形がないので $u$ と $w$ は隣接せず、$x\neq y$ が $u,w$ の共通の隣接頂点になる。隣接しない相異なる $u,w$ は交わる 2 元部分集合で、$u=ab$、$w=ac$ と書けるが、$u,w$ の両方と交わらない 2 元部分集合は $\{1,\dots,5\}\setminus\{a,b,c\}$ の 1 個しかない。
$12,34,15,23,45,12$ は長さ $5$ の閉路である。
したがって Petersen グラフの内周は $5$ である（図 1 の左）。

左はPetersenグラフで、外側の赤い5角形が長さ5の閉路。右は頂点12から距離1の3頂点と距離2の6頂点を並べた図で、青い辺をたどると10頂点すべてに重なりなく届く。点線は残りの辺。

超立方体と木

超立方体 $Q_n$（$n\ge2$。連結グラフの記事の例「超立方体」）の内周は $4$ である。1 歩ごとに列の中の $1$ の個数の偶奇が変わるので、閉歩道の長さは偶数で、三角形はない。一方 $00\cdots0,\ 10\cdots0,\ 110\cdots0,\ 010\cdots0$ は長さ $4$ の閉路である。
木と森は閉路をもたない。木 $T$ に、$T$ で隣接しない 2 頂点を結ぶ辺を 1 本加えると、閉路がちょうど 1 つできる（木の記事の命題「木に辺を1本加えるとちょうど1つの閉路ができる」）。
位数 $2m$ の二面体群の Coxeter 複体は、$2m$ 個の頂点をもつ閉路（$2m$ 角形の境界）である（Coxeter複体の記事の例「二面体群のCoxeter複体」）。

性質

閉路の存在

最小次数と長い閉路

有限グラフ $G$ の最小次数 $\delta(G)$ が $2$ 以上ならば、$G$ は長さ $\delta(G)+1$ 以上の閉路をもつ。

$G$ の道のうち長さが最大のもの $P:\ v_0,v_1,\dots,v_k$ をとる（$G$ は有限なので道は有限個）。$v_0$ の隣接頂点 $w$ が $P$ の上になければ、$w,v_0,v_1,\dots,v_k$ はより長い道になり、$P$ の最大性に反する。よって $v_0$ の隣接頂点はすべて $v_1,\dots,v_k$ の中にあり、その個数は $\delta(G)$ 以上である。そのうち添字が最大のものを $v_j$ とすると $j\ge\delta(G)\ge2$ であり、$v_0,v_1,\dots,v_j,v_0$ は長さ $j+1\ge\delta(G)+1\ge3$ の閉路である。$\square$

辺の本数と閉路

$n\ge1$ 頂点、連結成分 $c$ 個の有限グラフ $G$ の辺が $n-c+1$ 本以上なら、$G$ は閉路をもつ。特に辺が $n$ 本以上なら閉路をもつ。

閉路をもたなければ $G$ は森であり、連結グラフの記事の定理「辺の本数の下界と森」により辺はちょうど $n-c$ 本である。$n\ge1$ なら $c\ge1$ なので $n\ge n-c+1$ である。$\square$

$n$ 頂点の木は $n-1$ 本の辺をもち閉路をもたないので、「$n$ 本以上」は「$n-1$ 本以上」に弱められない。thm-graph-cycle-min-degree は有限性を外すと成り立たない。整数全体を頂点とし $i$ と $i+1$ を結んだグラフは、すべての頂点の次数が $2$ であるが閉路をもたない。閉路があれば、その頂点のうち最大の整数 $m$ は閉路の中で 2 つの頂点と隣接するはずだが、$m$ の隣接頂点は $m-1$ と $m+1$ だけで、$m+1$ は閉路にないからである。

橋と閉路

橋

有限グラフ $G$ の辺 $e$ が橋（bridge）であるとは、$e$ を除いたグラフ $G-e$ の連結成分の個数が $G$ より多いことをいう。

連結グラフの記事の補題「辺を 1 本加えたときの連結成分」により、辺を 1 本除くと連結成分の個数は変わらないか $1$ 増えるかのどちらかであり、橋とは $1$ 増える辺のことである。

閉路に含まれる辺と橋

有限グラフ $G$ の辺 $e=uv$ について、$e$ がある閉路に含まれることと、$e$ が橋でないことは同値である。

$e$ が閉路に含まれるなら、全域木の記事の補題「閉路上の辺を除いても連結成分は変わらない」により、$G$ で歩道で結ばれる 2 頂点は $G-e$ でも歩道で結ばれる。よって $G-e$ と $G$ の同値類は同じで、$e$ は橋でない。
逆に $e$ が橋でないとする。$u$ と $v$ が $G-e$ の異なる同値類に属したとすると、連結グラフの記事の補題「辺を 1 本加えたときの連結成分」により $G=(G-e)+e$ の連結成分は $G-e$ より $1$ 少なく、$e$ は橋になって矛盾する。よって $G-e$ に $u$ と $v$ を結ぶ道 $P:\ u=w_0,w_1,\dots,w_k=v$ がある。$e$ は $G-e$ の辺でないので $k\ge2$ であり、$w_0,w_1,\dots,w_k,w_0$ は辺 $e=w_kw_0$ を含む長さ $k+1\ge3$ の閉路である。$\square$

森と橋

有限グラフが森であることと、すべての辺が橋であることは同値である。特に、連結グラフが木であることと、どの辺を除いても連結でなくなることは同値である。

thm-graph-cycle-bridge により、橋でない辺があることと、閉路に含まれる辺があること、すなわち閉路をもつことは同値である。後半は、連結グラフ $G$ の辺 $e$ について、$e$ が橋であることと $G-e$ が連結でないことが同値であることによる。$\square$

後半は木の記事の命題「木から辺を1本除くとちょうど2つの連結成分に分かれる」の逆も含んでいる。

奇閉路と二部グラフ

奇数の長さの閉歩道は奇閉路を含む

グラフの長さが奇数の閉歩道 $W$ に対し、$W$ の辺だけを使う奇閉路がある。

長さ $\ell$ についての帰納法で示す。$W:\ w_0,w_1,\dots,w_\ell=w_0$ とする。ループがないので $\ell\neq1$、よって $\ell\ge3$ である。$w_0,\dots,w_{\ell-1}$ が相異なれば $W$ 自身が奇閉路である。そうでなければ $w_i=w_j$ となる $0\le i< j\le\ell-1$ があり、
$$ W_1:\ w_i,w_{i+1},\dots,w_j,\qquad W_2:\ w_0,\dots,w_i,w_{j+1},\dots,w_\ell $$
はどちらも閉歩道である（$W_2$ では $w_i=w_j$ と $w_j$ に隣接する $w_{j+1}$ をつなぐ）。長さはそれぞれ $j-i$ と $\ell-(j-i)$ で、どちらも $1$ 以上 $\ell-1$ 以下であり、和が奇数 $\ell$ なので一方は奇数である。その閉歩道は $W$ の辺だけを使い、帰納法の仮定により $W$ の辺だけを使う奇閉路を含む。$\square$

この命題から、グラフが奇閉路をもたないことと、長さが奇数の閉歩道をもたないことは同値である（閉路は閉歩道なので逆向きは明らか）。二部グラフの記事の定理「閉路の長さによる特徴付け」は、これらが二部グラフであることと同値であることを示している。長さが偶数の閉歩道については同様のことは成り立たない。辺 $uv$ の往復 $u,v,u$ は長さ $2$ の閉歩道だが、閉路を含まない。

閉路空間

2 元からなる有限体 $\mathbb{F}_2=\{0,1\}$ を係数とするベクトル空間で、閉路どうしの関係を調べる。有限グラフ $G=(V,E)$ の辺の部分集合全体は、対称差 $F+F':=(F\setminus F')\cup(F'\setminus F)$ を和として $\mathbb{F}_2$ 上のベクトル空間 $\mathbb{F}_2^E$ になる（部分集合 $F$ を、$F$ の辺で $1$、それ以外で $0$ をとる関数と同一視する）。頂点の部分集合全体 $\mathbb{F}_2^V$ も同様である。辺 $uv$ を $\{u\}+\{v\}=\{u,v\}$ に写す線形写像 $\partial\colon\mathbb{F}_2^E\to\mathbb{F}_2^V$ を考えると、$\partial F$ は全域部分グラフ $(V,F)$ で次数が奇数の頂点の集合である（頂点 $x$ は $F$ の辺のうち $x$ に接続するものの本数だけ数えられ、$2$ を法として足される）。

閉路空間

有限グラフ $G=(V,E)$ に対し、$\partial$ の核
$$ \mathcal{Z}(G):=\ker\partial=\{F\subset E\mid (V,F)\text{ のすべての頂点の次数が偶数}\} $$
を $G$ の閉路空間（cycle space）という。

閉路の辺集合は、閉路上の頂点で次数 $2$、それ以外で次数 $0$ なので $\mathcal{Z}(G)$ に属する。辺を共有しない閉路の辺集合の和集合も $\mathcal{Z}(G)$ に属する。逆も成り立つ。

偶数次数の辺集合は閉路に分かれる

$F\in\mathcal{Z}(G)$ が空でなければ、$F$ は辺を共有しない有限個の閉路の辺集合の和集合である。

$\lvert F\rvert$ についての帰納法で示す。$(V,F)$ で次数が正の頂点と $F$ の辺からなるグラフ $H$ は、すべての頂点の次数が $2$ 以上の偶数なので、thm-graph-cycle-min-degree により閉路 $Z$ をもつ。$Z$ の辺集合を $F_Z$ とすると、$F\setminus F_Z=F+F_Z$ は $\mathcal{Z}(G)$ の 2 元の和なので $\mathcal{Z}(G)$ に属し、$\lvert F\rvert$ より元の個数が少ない。空なら $F=F_Z$ であり、空でなければ帰納法の仮定により閉路に分かれるので、$Z$ を加えればよい。$\square$

閉路空間の次元は、グラフの全域的な森から具体的な基底を作って求められる。$G$ の各連結成分は連結なので全域木をもつ（全域木の記事の定理「全域木の存在」）。それらを合わせた森 $T$ を $G$ の全域森という。$G$ が $c$ 個の連結成分をもつとき、$T$ は $n=\lvert V\rvert$ 頂点で連結成分 $c$ 個の森なので、辺はちょうど $n-c$ 本である（連結グラフの記事の定理「辺の本数の下界と森」）。$e=uv\in E\setminus T$ に対し、$u,v$ は同じ連結成分に属し、その成分の全域木に $e$ を加えると閉路がちょうど 1 つできる（木の記事の命題「木に辺を1本加えるとちょうど1つの閉路ができる」。$e\notin T$ で単純グラフなので $u,v$ は木で隣接しない）。この閉路を $e$ の $T$ に関する基本閉路といい、その辺集合を $Z_e$ と書く。$Z_e$ に含まれる $T$ にない辺は $e$ だけである。

閉路空間の次元と基本閉路

$n$ 頂点、$m$ 辺、連結成分 $c$ 個の有限グラフ $G$ について
$$ \dim_{\mathbb{F}_2}\mathcal{Z}(G)=m-n+c $$
であり、全域森 $T$ に関する基本閉路の辺集合 $Z_e$（$e\in E\setminus T$）は $\mathcal{Z}(G)$ の基底である。

段 1（基本閉路は 1 次独立）。$E\setminus T$ の空でない部分集合 $A$ について、$\sum_{e\in A}Z_e$ は $A$ の各辺 $e$ をちょうど 1 回含む（$T$ にない辺を含む $Z_{e'}$ は $e'=e$ だけ）ので $0$ でない。よって $Z_e$（$e\in E\setminus T$）は線形独立で、その個数は $m-(n-c)$ である。
段 2（$\partial$ の像）。$G$ の連結成分の頂点集合を $C_1,\dots,C_c$ とし、$U:=\{X\subset V\mid \text{各 }i\text{ で }\lvert X\cap C_i\rvert\text{ は偶数}\}$ とおく。辺 $uv$ の両端は同じ $C_i$ に属するので $\partial(uv)=\{u,v\}\in U$、よって $\operatorname{im}\partial\subset U$ である。逆に $X\in U$ の各 $X\cap C_i$ の元を 2 つずつ組にすると、$X$ は同じ成分の 2 頂点の対 $\{u,v\}$ の和になる。$u$ と $v$ を結ぶ道の辺集合 $F$ について、道の途中の頂点は 2 本の辺に接続するので $\partial F=\{u,v\}$ である。よって $U\subset\operatorname{im}\partial$ であり、$\operatorname{im}\partial=U$ である。$U$ は、各 $C_i$ の頂点 $r_i$ を 1 つ固定すると、$r_i$ 以外の頂点の属し方を自由に選び $r_i$ の属し方で偶奇を合わせたもの全体なので、$\dim U=\sum_i(\lvert C_i\rvert-1)=n-c$ である。
段 3。線形写像の記事の定理「次元定理の言明」により $\dim\ker\partial=m-\dim\operatorname{im}\partial=m-n+c$ である。段 1 の $m-n+c$ 個の元は $\mathcal{Z}(G)$ の中の 1 次独立な元で、個数が次元に等しいので基底である。$\square$

$m-n+c$ を $G$ の閉路階数（cyclomatic number）ともいう。$m-n+c=0$ であることは $\mathcal{Z}(G)=0$、すなわち閉路をもたないことと同値であり、連結グラフの記事の定理「辺の本数の下界と森」の等号の場合と一致する。

$K_4$ の閉路空間

$K_4$ の頂点を $0,1,2,3$ とする。$n=4$、$m=6$、$c=1$ なので $\dim\mathcal{Z}(K_4)=3$ である。頂点 $0$ を中心とする星 $T=\{01,02,03\}$ は全域木で、木にない辺 $12,13,23$ の基本閉路は三角形 $012$、$013$、$023$ である（図 2）。その和は
$$ \{01,12,02\}+\{01,13,03\}+\{02,23,03\}=\{12,13,23\} $$
で、残りの三角形 $123$ になる。$\mathcal{Z}(K_4)$ は $2^3=8$ 個の元をもち、$0$ 以外の 7 個はちょうど ex-graph-cycle-complete の 7 個の閉路（三角形 4 個と長さ $4$ の閉路 3 個）の辺集合である。たとえば長さ $4$ の閉路 $0,1,2,3,0$ の辺集合は $\{01,12,02\}+\{02,23,03\}$ である。

K4の頂点0を中心とする全域木（青）と、木にない辺12・13・23のそれぞれが作る基本閉路（赤）。3つの基本閉路の辺集合を2を法として足すと、残りの三角形123になる。

内周と頂点の個数

内周 5 以上のグラフの頂点の個数

$d\ge1$ とし、有限グラフ $G$ の最小次数が $d$ 以上で、内周が $5$ 以上（長さ $3$ と $4$ の閉路をもたない）とする。このとき $G$ の頂点は $1+d^2$ 個以上である。さらに $d\ge2$ でちょうど $1+d^2$ 個なら、$G$ は $d$-正則（すべての頂点の次数が $d$）で、隣接する 2 頂点は共通の隣接頂点をもたず、隣接しない相異なる 2 頂点は共通の隣接頂点をちょうど 1 つもつ。

頂点 $v$ を 1 つとり、その隣接頂点の集合を $N(v)$ とする。$u\in N(v)$ に対し $M_u:=N(u)\setminus\{v\}$ とおくと $\lvert M_u\rvert\ge d-1$ である。

$M_u$ は $\{v\}\cup N(v)$ と交わらない。$w\in M_u\cap N(v)$ なら $v,u,w$ が三角形になるからである。
$u\neq u'$ なら $M_u\cap M_{u'}=\emptyset$ である。$w\in M_u\cap M_{u'}$ なら、$w\notin\{v\}\cup N(v)$ なので $v,u,w,u',v$ は長さ $4$ の閉路になるからである。
よって
$$ \lvert V\rvert\ge1+\lvert N(v)\rvert+\sum_{u\in N(v)}\lvert M_u\rvert\ge1+\deg v+\deg v\cdot(d-1)=1+d\deg v\ge1+d^2 . $$
$\lvert V\rvert=1+d^2$ なら、どの $v$ についても等号が成り立つので $\deg v=d$ であり、$V=\{v\}\cup N(v)\cup\bigcup_uM_u$、すなわちすべての頂点は $v$ から距離 $2$ 以内にある。隣接する 2 頂点の共通の隣接頂点は三角形を作るのでない。隣接しない相異なる 2 頂点 $v,w$ は距離 $2$ なので共通の隣接頂点をもち、2 つあれば長さ $4$ の閉路ができるので、ちょうど 1 つである。$\square$

等号の場合のグラフは、Conway's 99-graph problem の記事の定義「強正則グラフのパラメータ」の $\mathrm{srg}(1+d^2,d,0,1)$ である（$d\ge2$ なら $1+d^2>d+1$ なので完全グラフではない）。$C_5$（$d=2$）と Petersen グラフ（$d=3$、$1+9=10$）は等号を満たす。図 1 の右は、Petersen グラフの頂点 $12$ から、隣接頂点 3 個とそれぞれの残りの隣接頂点 2 個ずつをたどると、10 頂点すべてに重なりなく届くことを示している。Hoffman と Singleton は、$\mathrm{srg}(v,k,0,1)$ が存在するなら $(v,k)$ は $(5,2)$、$(10,3)$、$(50,7)$、$(3250,57)$ のいずれかであることを示した（BH11 Theorem 9.1.5、pdf p. 127）。同書は、最初の 3 つが 5 角形・Petersen グラフ・Hoffman–Singleton グラフでただ 1 通りに実現され、最後の場合の存在は分かっていないと述べている。この証明は固有値の重複度が整数であることを使うもので、この記事では扱わない。Conway's 99-graph problem は $\mathrm{srg}(99,14,1,2)$ の存在を問う問題で、上の証明と同じく 1 頂点のまわりの頂点を 2 通りに数える議論（同記事の命題「パラメータの基本関係」）が基本になる。

反例と用語の区別

閉路の定義と上の定理の仮定を外すと、次のように結論が崩れる。

外す条件	反例	成り立たなくなること
閉路の長さ $\ell\ge3$	辺 $uv$ の往復 $u,v,u$	閉歩道なら閉路（グラフの記事の例「反例：長さ 2 の閉歩道」）
途中の頂点が相異なる	1 点を共有する 2 つの三角形を続けて一周する閉小道	閉小道なら閉路（同じ例）
thm-graph-cycle-min-degree の有限性	整数全体を頂点とする道	最小次数 $2$ 以上なら閉路をもつ
cor-graph-cycle-edges の「辺が $n$ 本以上」	$n$ 頂点の木（辺 $n-1$ 本）	閉路をもつ
thm-graph-cycle-girth-five の内周 $5$ 以上	$K_4$、$K_{3,3}$、$Q_3$（$d=3$）	頂点が $1+d^2=10$ 個以上

最後の行の 3 つのグラフはどれも $3$-正則で、頂点はそれぞれ $4$、$6$、$8$ 個である。$K_4$ の内周は $3$、$K_{3,3}$ と $Q_3$ の内周は $4$ である（$K_{3,3}$ は二部グラフなので奇閉路がなく、部集合から 2 頂点ずつとれば長さ $4$ の閉路がある）。
「閉路」を含む名前の概念と、経路の条件を比べると次のようになる。

概念	頂点の再訪	辺の再使用	全体を通る条件
閉歩道	可	可	なし
閉小道	可	不可	なし
閉路	不可（始点に戻るだけ）	不可	なし（長さ $3$ 以上）
Euler 閉路	可	不可	すべての辺をちょうど 1 回
Hamilton 閉路	不可（始点に戻るだけ）	不可	すべての頂点をちょうど 1 回

Euler 閉路は同じ頂点を何度通ってもよいので、一般には閉路ではなく閉小道である（Euler閉路の記事の注意「閉路という語とのずれ」）。Hamilton 閉路は閉路の一種であり、すべての頂点を通る閉路のことである（Hamilton閉路）。Petersen グラフは長さ $5$ の閉路をもつが Hamilton 閉路をもたないことが知られている（BH11 §4.5.1、pdf p. 81。固有値の交錯を使う証明）。

多重グラフと有向グラフの閉路

平行辺やループを許すグラフでは、歩道を頂点と辺の交互列として扱い、ループ 1 本を長さ $1$ の閉路、平行辺 2 本を長さ $2$ の閉路とみなす流儀がある（全域木の記事の定義「ループを許す多重グラフと基本用語」）。この流儀では閉路の長さは $1$ 以上であり、thm-graph-cycle-min-degree の「長さ $\delta+1$ 以上」はそのままでは成り立たない（2 頂点を 3 本の平行辺で結んだグラフは最小次数 $3$ だが、閉路の長さは $2$ である）。有向グラフでは、辺の向きに沿った有向閉路を考え、長さ $1$・$2$ の有向閉路も許す（有向グラフの記事の定義「有向歩道・有向道・有向閉路」）。基礎グラフの閉路と有向閉路は一般に一致しない（同記事の例「反例：基礎グラフの閉路と有向閉路のずれ」）。

用語

文献によっては、この記事の閉路を「サイクル」「回路」とよび、閉小道を「閉歩道」とよぶことがある（グラフの記事の補足）。「サイクル」は置換の巡回置換や代数幾何学の代数的サイクルの意味でも使われるので、グラフの閉路を指すときは文脈を明示する。英語では cycle のほか、閉路をもたないことを acyclic という。