退化数
概要
退化数（degeneracy）とは、有限グラフ $G$ のすべての部分グラフの最小次数の最大値であり、どの部分グラフにも次数 $k$ 以下の頂点があるとき $G$ を $k$-退化という。$k$-退化であることは、各頂点の後ろにある隣接頂点が $k$ 個以下になる頂点の並べ方があることや、各頂点から出る辺が $k$ 本以下の非巡回な向き付けがあることと同値で、最小次数の頂点を 1 つずつ除く手順により退化数と並べ方が線形時間で求まる。$k$-退化なグラフ（$n\ge k$ 頂点）の辺は $kn-k(k+1)/2$ 本以下で、彩色数は退化数に $1$ を足した数以下である。森は $1$-退化、平面グラフは $5$-退化である。
グラフのどの部分を取り出しても、その中に次数の小さい頂点がある、という性質でグラフの「疎らさ」を測るのが 退化数（degeneracy）である。グラフ $G$ が $k$-退化 であるとは、頂点を 1 個以上もつどの部分グラフにも次数 $k$ 以下の頂点があることをいい、そのような最小の $k$ を退化数という。森は $1$-退化、平面グラフは $5$-退化、ペニーグラフ は $3$-退化である。
この記事では、$k$-退化であることが「各頂点の後ろにある隣接頂点が $k$ 個以下になる頂点の並べ方がある」こと、「各頂点から出る辺が $k$ 本以下の非巡回な向き付けがある」ことなどと同値であることを示す（thm-dgn-equiv）。次に、最小次数の頂点を 1 つずつ除く手順が退化数と並べ方を求め、頂点の個数と辺の本数の和に比例する手間で実行できることを証明する（thm-dgn-peel、prop-dgn-linear）。さらに $k$-退化なグラフの辺の本数の上界を与える（thm-dgn-edges）。彩色数は退化数に $1$ を足した数以下である（彩色数 の命題「部分グラフの最小次数による上界」）。
定義
この記事のグラフは有限の単純無向グラフ $G=(V,E)$ で、頂点を 1 個以上もつとし、$n=\lvert V\rvert$、$m=\lvert E\rvert$ と書く。頂点 $v$ の $G$ での次数を $\deg_G(v)$、最小次数を $\delta(G)$、最大次数を $\Delta(G)$ と書く（次数(グラフ)）。部分グラフは頂点を 1 個以上もつものだけを考える。
整数 $k\ge0$ について、$G$ のすべての部分グラフ $H$ が $\delta(H)\le k$ を満たすとき、$G$ は $k$-退化（$k$-degenerate）であるという。$G$ が $k$-退化となる最小の $k$ を $G$ の 退化数 といい、$\operatorname{degen}(G)$ と書く。すなわち
$$
\operatorname{degen}(G)=\max\{\delta(H): H\ \text{は}\ G\ \text{の部分グラフ}\}
$$
である。
部分グラフ $H$ は、同じ頂点集合の 誘導部分グラフ $G[V(H)]$ に含まれ、各頂点の次数は $H$ のほうが小さいか等しいので $\delta(H)\le\delta(G[V(H)])$ である。したがって定義の「すべての部分グラフ」は「すべての誘導部分グラフ」に置き換えてよい。ペニーグラフ の命題「次数が 3 以下の頂点の存在」は誘導部分グラフの形で $3$-退化を述べている。
$H=G$ とすれば $\delta(G)\le\operatorname{degen}(G)$ であり、どの部分グラフの最小次数も $\Delta(G)$ 以下なので $\operatorname{degen}(G)\le\Delta(G)$ である。
整数 $j\ge0$ について、最小次数が $j$ 以上の誘導部分グラフの頂点集合すべての和集合を $C_j$ とし、$C_j\ne\emptyset$ のとき $G[C_j]$ を $G$ の $j$-コア（$j$-core）という。
最小次数が $j$ 以上の誘導部分グラフ $G[A]$、$G[B]$ について、$A\cup B$ の頂点 $v\in A$ の $G[A\cup B]$ での次数は $G[A]$ での次数以上なので、$G[A\cup B]$ の最小次数も $j$ 以上である。よって $C_j\ne\emptyset$ なら $G[C_j]$ 自身が最小次数 $j$ 以上で、そのような誘導部分グラフのうち最大のものである。
直感
最小次数 $\delta(G)$ はグラフ全体のどこか 1 か所に疎らな頂点があることしか言わない。次数の大きい頂点が密に集まった部分（たとえば完全グラフ）が隠れていても、そこから離れた所に次数 $1$ の頂点があれば $\delta(G)=1$ になる。退化数はすべての部分グラフの最小次数の最大なので、「いちばん密に詰まった部分がどれだけ密か」を測る。言い換え（thm-dgn-equiv）の並べ方で見ると、$k$-退化なグラフは、次数 $k$ 以下の頂点を 1 つずつ剥がしていけば最後まで剥がしきれるグラフである。剥がす順の逆に頂点を戻していく帰納法が使えることが、彩色や辺の数え上げに退化数が効く理由である。
- $G$ の部分グラフ $H$ について $\operatorname{degen}(H)\le\operatorname{degen}(G)$ である。
- 頂点を 2 個以上もつ $G$ の頂点 $v$ について $\operatorname{degen}(G)-1\le\operatorname{degen}(G-v)\le\operatorname{degen}(G)$ である。
- $G$ に辺 $e$ を 1 本加えたグラフ $G+e$ について $\operatorname{degen}(G)\le\operatorname{degen}(G+e)\le\operatorname{degen}(G)+1$ である。
1：$H$ の部分グラフは $G$ の部分グラフである。
2：右の不等式は 1 による。$d:=\operatorname{degen}(G)$ とし、$\delta(H)=d$ となる部分グラフ $H$ をとる。$v\notin V(H)$ なら $H$ は $G-v$ の部分グラフである。$v\in V(H)$ で $H$ が $v$ だけなら $d=0$ で明らか。そうでなければ $H-v$ の各頂点の次数は $H$ での次数から高々 $1$ 減るので $\delta(H-v)\ge d-1$ であり、$H-v$ は $G-v$ の部分グラフである。
3：左は 1 による。$G+e$ の部分グラフ $H$ について、$e$ を除いた $H-e$（$e\in E(H)$ のとき）は $G$ の部分グラフで、各頂点の次数は高々 $1$ 減るので、$\delta(H)\le\delta(H-e)+1\le\operatorname{degen}(G)+1$ である。$\square$
同値な言い換え
頂点の並べ方 $v_1,\dots,v_n$ について、$v_i$ と隣接する $v_{i+1},\dots,v_n$ の個数を $v_i$ の 後ろの次数 という。辺の 向き付け とは、各辺 $uv$ を $u\to v$ か $v\to u$ のどちらかの向きの辺にすることで、有向閉路ができないものを 非巡回 な向き付けという。
整数 $k\ge0$ について、次は同値である。
- $G$ は $k$-退化である。
- どの頂点の後ろの次数も $k$ 以下である並べ方がある。
- どの頂点から出る辺も $k$ 本以下である非巡回な向き付けがある。
- $G$ の $(k+1)$-コアは存在しない（$C_{k+1}=\emptyset$）。
（1 ⇒ 2）$W_1:=V$ とし、$i=1,\dots,n$ について $G[W_i]$ の次数 $k$ 以下の頂点を $v_i$ とし、$W_{i+1}:=W_i\setminus\{v_i\}$ とする（1 により選べる）。$W_i=\{v_i,\dots,v_n\}$ なので、$v_i$ の後ろの次数は $\deg_{G[W_i]}(v_i)\le k$ である。
（2 ⇒ 3）辺 $v_iv_j$（$i< j$）を $v_i\to v_j$ と向ける。$v_i$ から出る辺の本数は後ろの次数で $k$ 以下である。有向閉路をたどると添字は真に増え続けるので、出発点に戻れない。よって非巡回である。
（3 ⇒ 1）部分グラフ $H$ をとり、向き付けを $H$ の辺に制限する。$H$ のどの頂点にも $H$ の中で入る辺があるとすると、入る辺を逆向きにたどり続けることができ、頂点は有限個なので同じ頂点に戻り、有向閉路ができて矛盾する。よって $H$ の中で入る辺のない頂点 $v$ があり、$\deg_H(v)$ は $H$ の中で $v$ から出る辺の本数で、$k$ 以下である。
（1 ⇔ 4）4 は「最小次数が $k+1$ 以上の誘導部分グラフがない」こと、すなわちすべての誘導部分グラフの最小次数が $k$ 以下であることで、定義の後の注意により 1 と同値である。$\square$
2 の並べ方を逆順にすると、各頂点の前にある隣接頂点が $k$ 個以下になる。Diestel はこの形で、各頂点の前の隣接頂点が $\ell$ 個未満となる並べ方がある最小の $\ell$ を colouring number $\operatorname{col}(G)$ とよび、$\operatorname{col}(G)=\max_{H}\delta(H)+1$ を示している（Die25 Proposition 5.2.2、p. 127）。thm-dgn-equiv の 1 ⇔ 2 により $\operatorname{col}(G)=\operatorname{degen}(G)+1$ である。2 の並べ方の逆順で 彩色数 の補題「貪欲彩色」を行うと、各頂点の色は $k+1$ 以下になる。これが 彩色数 の命題「部分グラフの最小次数による上界」
$$
\chi(G)\le\operatorname{degen}(G)+1
$$
である。また $G$ が $r$ 頂点の完全グラフを含めば、その部分グラフの最小次数は $r-1$ なので、クリーク数（クリーク）$\omega(G)$ について $\omega(G)\le\operatorname{degen}(G)+1$ である。
退化数を求める手順
$G_1:=G$ とし、$i=1,\dots,n$ について、$G_i$ の次数が最小の頂点 $u_i$ を 1 つ選び、その次数を $\delta_i:=\deg_{G_i}(u_i)=\delta(G_i)$ とし、$G_{i+1}:=G_i-u_i$（$u_i$ とそれに接続する辺を除いたグラフ）とする。
def-dgn-peel の手順で、$\operatorname{degen}(G)=\max_{1\le i\le n}\delta_i$ であり、$u_1,\dots,u_n$ はどの頂点の後ろの次数も $\operatorname{degen}(G)$ 以下である並べ方である。
$G_i$ は $G$ の部分グラフなので $\delta_i=\delta(G_i)\le\operatorname{degen}(G)$ である。逆に $k:=\max_i\delta_i$ とする。$G_i$ の頂点は $u_i,\dots,u_n$ なので、$u_i$ の後ろの次数は $\deg_{G_i}(u_i)=\delta_i\le k$ である。よってこの並べ方は thm-dgn-equiv の 2 を満たし、$G$ は $k$-退化で $\operatorname{degen}(G)\le k$ である。$\square$
各段の $\delta_i$ は単調とは限らない。各段で最小次数の頂点を選ぶことが要る（ex-dgn-peel-run、例と反例の表）。
隣接リストが与えられているとき、def-dgn-peel の手順は $O(n+m)$ 回の基本操作で実行できる。
各頂点の現在の次数 $\deg(v)$ と、$d=0,1,\dots,n-1$ について次数がちょうど $d$ の未削除の頂点の双方向リスト $B[d]$ を持ち、各頂点がどのリストのどこにあるかも記録する。最初の準備は $O(n+m)$ である。添字 $j$（最初は $0$）を、空でない $B[d]$ の最小の $d$ を探すために使う。
各段では、$B[j]$ が空なら $j$ を $1$ ずつ増やし、空でない $B[j]$ から頂点 $u$ を取り出す（$\delta_i=j$）。$u$ の未削除の隣接頂点 $v$ について $\deg(v)$ を $1$ 減らし、$v$ を $B[\deg(v)+1]$ から $B[\deg(v)]$ へ移す。これは $O(\deg_G(u))$ である。その段の前、未削除の頂点の次数はすべて $\delta_i$ 以上で、各頂点の次数は高々 $1$ しか減らないので、次の段の最小次数は $\delta_i-1$ 以上である。そこで $j:=\max\{j-1,0\}$ として次の段に進めば、$j$ を増やして探す途中で空でない $B[d]$ を飛ばすことはない。
$j$ は $0$ 以上 $n-1$ 以下にとどまり、減るのは各段で高々 $1$ なので、増やす回数の合計は $(n-1)+n$ 以下である。隣接頂点の更新の合計は $\sum_u\deg_G(u)=2m$ なので、全体は $O(n+m)$ である。$\square$
ELS10 §2.1（pp. 3–4）は、この手順で退化数と並べ方が求まり、次数ごとのリストで線形時間に実行できることを述べている。
頂点 $a,b,c,d$ を互いに結んだ $K_4$ に、$a,b$ と隣接する頂点 $e$ と、$e$ と隣接する頂点 $f$ を加えたグラフ $G$（$6$ 頂点、辺は $6+2+1=9$ 本）を考える。次数は $a,b$ が $4$、$c,d$ が $3$、$e$ が $3$、$f$ が $1$ である。
| 段 | 除く頂点 | その時の次数 $\delta_i$ | 残りの頂点の次数 |
|---|---|---|---|
| 1 | $f$ | $1$ | $a{:}4,\ b{:}4,\ c{:}3,\ d{:}3,\ e{:}2$ |
| 2 | $e$ | $2$ | $a{:}3,\ b{:}3,\ c{:}3,\ d{:}3$ |
| 3 | $a$ | $3$ | $b{:}2,\ c{:}2,\ d{:}2$ |
| 4 | $b$ | $2$ | $c{:}1,\ d{:}1$ |
| 5 | $c$ | $1$ | $d{:}0$ |
| 6 | $d$ | $0$ |
$\max\delta_i=3$ なので thm-dgn-peel により $\operatorname{degen}(G)=3$ で、$K_4$ が最小次数 $3$ の部分グラフである。$\delta_i$ は $1,2,3,2,1,0$ と増えてから減る。並べ方 $f,e,a,b,c,d$ で辺を前から後ろへ向けると、各頂点から出る辺は $1,2,3,2,1,0$ 本である。$G$ 自身の最小次数は $1$ で、退化数より小さい。
辺の本数
$G$ が $k$-退化で $n\ge k$ なら
$$
m\le kn-\frac{k(k+1)}{2}
$$
である。等号は、$k$ 頂点の完全グラフ $K_k$ のすべての頂点を、互いに隣接しない $n-k$ 個の頂点のすべてと結んだグラフで成り立つ。
thm-dgn-equiv の 2 の並べ方 $v_1,\dots,v_n$ をとる。各辺は前の端点の後ろの次数として 1 回ずつ数えられるので、$m$ は後ろの次数の和である。$v_i$ の後ろの次数は $k$ 以下で、後ろにある頂点の個数 $n-i$ 以下でもあるので
$$
m\le\sum_{i=1}^{n}\min\{k,n-i\}=k(n-k)+\sum_{t=0}^{k-1}t=kn-k^2+\frac{k(k-1)}{2}=kn-\frac{k(k+1)}{2}
$$
である（$i\le n-k$ では $k$、$i=n-k+t+1$（$0\le t\le k-1$）では $k-1-t$）。等号の例では、隣接しない $n-k$ 個の頂点を先に、$K_k$ の頂点を後に並べると、前者の後ろの次数は $k$、後者は $k-1,k-2,\dots,0$ で、辺の本数 $k(n-k)+k(k-1)/2$ は右辺に等しい。この並べ方により、このグラフは $k$-退化である。$\square$
この上界は ELS10 Lemma 1（p. 4）にある。$k=\operatorname{degen}(G)$ とおくと $k\le\Delta(G)\le n-1$ なので定理が使え、$m< kn$ から
$$
\operatorname{degen}(G)>\frac{m}{n}
$$
である（$m\ge1$ のとき）。平均次数 $2m/n$ の半分より退化数は大きい。逆向きの比較もある。たとえば平面グラフは $5$-退化（下の表）なので $n\ge5$ で $m\le5n-15$ が従うが、平面グラフ の系「単純平面グラフの辺数の上界」の $3n-6$ のほうが小さい。
例
$G$ が森（閉路を含まないグラフ）であることと、$\operatorname{degen}(G)\le1$ であることは同値である。
森の部分グラフは森である。頂点を 1 個以上もつ森 $H$ で、辺の本数が最大の道（長さ $0$ も含む）の端点 $v$ をとると、$v$ の隣接頂点は道の上の隣の頂点だけで、高々 1 個である。ほかの隣接頂点 $x$ が道の上にあれば閉路ができ、道の外にあれば道を延ばせるからである。よって $\delta(H)\le1$ である。逆に $G$ が閉路を含めば、その閉路の最小次数は $2$ で、$\operatorname{degen}(G)\ge2$ である。$\square$
| グラフ | 退化数 | 理由 |
|---|---|---|
| $n$ 頂点の完全グラフ $K_n$ | $n-1$ | $\delta=\Delta=n-1$ |
| $r$-正則グラフ（正則グラフ。$r=3$ の Petersenグラフ など） | $r$ | $\delta(G)\le\operatorname{degen}(G)\le\Delta(G)$ |
| 完全二部グラフ $K_{a,b}$（$1\le a\le b$） | $a$ | $\delta=a$。$b$ 個の側を先に並べると後ろの次数は $a$ 以下 |
| 森（辺あり） | $1$ | prop-dgn-forest |
| $a\times b$ の格子グラフ（$a,b\ge2$） | $2$ | 部分グラフの頂点のうち座標 $(x,y)$ が辞書式で最大のものは、左と下の 2 個以下としか隣接しない。4 頂点の閉路を含むので $2$ 以上 |
| 外平面グラフ（閉路を含むもの） | $2$ | 同記事の定理「次数 2 以下の頂点」と系「マイナーをとる操作と外平面性」。閉路を含むので $2$ 以上 |
| ペニーグラフ | $3$ 以下 | 同記事の命題「次数が 3 以下の頂点の存在」 |
| 平面グラフ | $5$ 以下 | 部分グラフも平面グラフで、彩色数 の系「平面グラフの 6 色彩色」の証明の議論で次数 $5$ 以下の頂点がある。正二十面体のグラフは $5$-正則で $5$ に等しい |
例と反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| すべての部分グラフで次数 $k$ 以下の頂点がある（$G$ 自身の最小次数だけを見る） | $K_5$ の 1 頂点に次数 $1$ の頂点を付けたグラフ | $\delta(G)\le k$ から $k$-退化が従うこと（$\delta(G)=1$ だが退化数は $4$） |
| 各段で次数が最小の頂点を除く（thm-dgn-peel） | 星 $K_{1,3}$ で中心を最初に除く | $\max_i\delta_i$ が退化数に等しいこと（最初の段が $3$ で、退化数は $1$） |
| $n\ge k$（thm-dgn-edges） | $k=3$、$1$ 頂点のグラフ（$3$-退化） | 辺の本数の上界（右辺は $3-6=-3< 0=m$） |
退化数による彩色数の上界は等号から遠いことがある。$K_{a,a}$ は 2 色で塗れるが、退化数は $a$ である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
