パスとサイクル
グラフ $G=(V, E)$ 上の長さ $n$ のパスとは、$G$ の相異なる $n+1$ 個の頂点を通る辺 $v_0 v_1, \ldots, v_{n-1} v_n$ からなるパスをいい、グラフ $G=(V, E)$ 上の長さ $n$ のサイクルとは、$G$ の相異なる $n$ 個の頂点を通る辺 $v_0 v_1, \ldots, v_{n-2} v_{n-1}, v_{n-1} v_0$ からなるサイクルをいう。
一般化
パスとサイクルについて、より一般的な概念も定義される。
- グラフ $G = (V, E)$ について、$G$ の歩道 (walk) とは、$V$ の(異ならなくともよい)頂点 $v_0, v_1, \ldots v_\ell$ と $E$ の辺 $e_1=v_0 v_1, e_2=v_1 v_2, \ldots, e_\ell=e_{\ell -1} e_\ell$、つまり $e_i$ が $v_{i-1}$ と $v_i$ をつなぐようなものの組のことをいう。このとき、この歩道は $v_0$ と $v_\ell$ を結ぶという。$\ell$ を、この歩道の長さ (length) という。
- グラフ $G = (V, E)$ について、$G$ の小道 (trail) とは、$V$ の歩道のうち、辺 $e_1, \ldots, e_\ell$ が相異なるものをいう（$v_i$ は相異ならなくてもよい。つまり同じ頂点を複数回通ってもよい）。$\ell$ を、この小道の長さという。
- グラフ $G = (V, E)$ について、$G$ の閉歩道 (circuit) とは、$V$ の小道のうち、$v_0=v_\ell$ となるものをいう。つまり (異ならなくともよい)頂点 $v_1, v_2, \ldots v_\ell$ と $E$ の異なる辺 $e_1=v_1 v_2, \ldots, e_{\ell -1}=v_{\ell-1} v_\ell, e_\ell=v_\ell v_1$、つまり $1 \leq i \leq \ell-1$ について $e_i$ が $v_i$ と $v_{i+1}$ をつなぎ、$e_\ell$ が $v_\ell$ と $v_1$ をつなぐようなものの組のことをいう。$\ell$ を、この閉歩道の長さという。
$G$ の小道のうち、頂点が $v_0, v_1, \ldots v_\ell$ が相異なるものが $G$ 上のパスとなる。また、$V$ の閉歩道のうち、$v_1, \ldots, v_\ell$ が相異なるものが $G$ 上のサイクルとなる。
$2$頂点 $u$, $v$ を結ぶ長さ $n$ の歩道が存在するとき、$u$, $v$ を結ぶ長さ $n$ 以下のパスが存在する。実際、$u$, $v$ を結ぶ長さ $n$ の歩道 $u=u_0, \ldots, u_n=v$ について、$u_i=u_j$ となる $i< j$ があるとき、$u_{i+1}, \ldots, u_{j-1}$ を取り除くことで、$u$, $v$ を結ぶ、長さが $n$ より小さい歩道ができる。これを繰り返すことで、$u$, $v$ を結ぶ長さ $n$ 以下のパスが必ずとれる。同様にして、$2$頂点 $u$, $v$ を結ぶ長さ $n$ の閉歩道が存在するとき、$u$, $v$ を結ぶ長さ $n$ 以下のサイクルが存在する。
サイクルに関する古典的な定理
サイクルについて、つぎのような事実が知られている。
グラフ $G = (V, E)$ の辺がサイクルに分割される $\Longleftrightarrow$ $G$ の各頂点の次数が偶数。
$E$ がサイクルに分割されているとする。サイクルの各頂点は次数 $2$ をもつから、各頂点 $v$ に接続する辺が $k_v$ 個のサイクルに分割されているとき、$d(v)=2k_v$ は偶数となる。
逆に、$G$ の各頂点の次数が偶数であるとき、グラフ $G = (V, E)$ の辺がサイクルに分割されることを、$e(G)$ に関する帰納法で示す。
$e(G)=0$ のときは、$0$ 個のサイクルに分割されていると考えることができる。
$e(G)>0$ とする。$G$ に含まれるパスで長さが最大のものをとり、それを $v_0, v_1, \ldots, v_\ell$ とおく。
$d(v_0)>0$ なので、仮定より $d(v_0)\geq 2$ となるから $v_1$ 以外に $v_0$ に隣接する頂点 $w$ がとれる。$w$ が $v_2, \ldots, v_\ell$ に含まれないとすると、$w, v_0, \ldots, v_\ell$ が $G$ に含まれるパスとなってしまうが、これは $v_0, v_1, \ldots, v_\ell$ が $G$ に含まれる最長のパスであることに反する。
よって、$w$ は $v_2, \ldots, v_\ell$ のいずれかと一致する。$w=v_s$ とおくと、$v_0, \ldots, v_s$ は $G$ に含まれるサイクルとなる。
$E$ から辺 $v_0 v_1, \ldots, v_{s-1} v_s, v_s v_0$ を取り除いたグラフを $H$ とおく。$v$ が $v_0, \ldots, v_s$ のいずれとも一致しないとき $N_H(v)=N_G(v)$ となる。つまり $v$ に接続する $G$ の辺は $H$ の辺のままである。よって $d_H(v)=d_G(v)$ となる。
一方、$v=v_i$ が $v_0, \ldots, v_s$ のいずれかであるとき、$N_H(v_i)=N_G(v_i)\setminus \{v_{i-1}, v_{i+1}\}$ （ただし $v_{s+1}=v_0$ とする）となるから、$d_H(v)=d_G(v)-2$ となる。
よって、$H$ の各頂点の次数も偶数であるから、帰納法の仮定より、$H$ の辺はサイクルに分割される。したがって、$G$ の辺は、$H$ の辺のサイクルへの分割に、サイクル $v_0, \ldots, v_s$ を加えたものに分割される。
$\abs{G}=n$ かつ、$e(G)>\floor{n^2/4}$ となるグラフは三角形を部分グラフにもつ。言い換えれば、三角形を部分グラフにもたない位数 $n$ のグラフの大きさは $\floor{n^2/4}$ 以下である。
$G$ が三角形を部分グラフにもたないグラフとする。このとき、$xy\in E$ ならば $x$ と $y$ の両方に隣接する頂点は存在しないから、
$$d(x)+d(y)\leq n$$
となる。すべての辺 $xy\in E$ について、これを加えると、
$$\sum_{xy\in E}d(x)+d(y)\leq n e(G)$$
となる。一方、各 $x\in E$ について、左辺の和にあらわれる $d(x)$ の回数は、$x$ の次数に等しい。つまり
$$\sum_{xy\in E}d(x)+d(y)=\sum_{x\in V}\sum_{y\in N(x)}d(x)=\sum_{x\in V}d(x)^2$$
となる。よって
$$\sum_{x\in V}d(x)^2\leq n e(G)$$
となる。
次数に関する定理1
より、
$$\sum_{x\in V}d(x)=2e(G)$$
となるから、Cauchyの不等式より
$$(2e(G))^2=\left(\sum_{x\in V}d(x)\right)^2\leq n\sum_{x\in V}d(x)^2\leq n^2 e(G)$$
が成り立つ。それで
$$e(G)\leq n^2/4$$
となる、$e(G)$ は整数だから
$$e(G)\leq\floor{n^2/4}$$
でなければならないことがわかる。
