次数(グラフ)
概要
次数(グラフ)（degree）とは、グラフ $G=(V,E)$ の頂点 $v$ に接続する辺の本数 $\deg_G(v)$、すなわち単純グラフでは $v$ に隣接する頂点の個数のことである。次数は 1 頂点だけから計算できる局所的な量であるが、全頂点の次数の総和は辺数の 2 倍に等しく（握手補題 $\sum_v\deg_G(v)=2|E|$）、その系として次数が奇数の頂点は偶数個である。最小次数 $\delta(G)$・最大次数 $\Delta(G)$・平均次数はグラフの疎密を表し、全頂点の次数が等しいグラフが正則グラフ、次数を非増加順に並べた列が次数列である。どの非負整数列が次数列になるかは Havel-Hakimi の定理で再帰的に判定でき、Erdős-Gallai の定理が不等式による特徴付けを与える。多重グラフでは平行辺を重複度込みで数え、有向グラフでは出次数と入次数を区別する。
定義
本記事では、特に断らない限り、ループも平行辺も持たない無向の単純グラフ $G=(V,E)$ を扱う。頂点の集合を $V=V(G)$、辺の集合を $E=E(G)$ と書き、辺 $\{u,v\}\in E$ を $uv$ とも書く。頂点 $v$ に隣接する頂点全体の集合（$v$ の近傍）を $N_G(v):=\{u\in V\mid uv\in E\}$ と書く。多重グラフと有向グラフの場合は def-degree-multigraph-directed で扱う。
グラフ $G=(V,E)$ の頂点 $v\in V$ の次数（degree）とは、$v$ に接続する辺の本数、すなわち $v$ を端点に持つ辺の個数
$$\deg_G(v):=|\{e\in E\mid v\in e\}|=|N_G(v)|$$
のことをいう。$d_G(v)$、$d(v)$ とも書く。次数 $0$ の頂点を孤立頂点（isolated vertex）、次数 $1$ の頂点を葉（leaf）または端頂点（end vertex）という。
単純グラフでは $v$ に接続する辺 $vu$ と隣接頂点 $u\in N_G(v)$ が 1 対 1 に対応するので、上の 2 つの表示は一致する。無限グラフでは次数は無限基数にもなりうるが、本記事では有限グラフを扱う。
空でない有限グラフ $G=(V,E)$ に対し、
$$\delta(G):=\min_{v\in V}\deg_G(v),\qquad \Delta(G):=\max_{v\in V}\deg_G(v)$$
をそれぞれ $G$ の最小次数（minimum degree）、最大次数（maximum degree）といい、
$$\overline{d}(G):=\frac{1}{|V|}\sum_{v\in V}\deg_G(v)$$
を $G$ の平均次数（average degree）という。
平均次数を $d(G)$ と書く文献もあるが（Die17 §1.2）、頂点の次数 $d(v)$ との混同を避けて本記事では $\overline{d}(G)$ と書く。頂点を持たないグラフでは最小値・最大値・平均値が定義できないので、空でないことを仮定した。
空でない有限グラフ $G$ が正則（regular）であるとは、すべての頂点の次数が等しいこと、すなわち $\delta(G)=\Delta(G)$ となることをいう。すべての頂点の次数が $k$ に等しいとき $G$ を $k$-正則グラフ（$k$-regular graph）という。$3$-正則グラフを立方グラフ（cubic graph）ともいう。
有限グラフ $G$ の次数列（degree sequence）とは、$G$ のすべての頂点の次数を非増加順に並べた列 $(d_1,d_2,\dots,d_n)$（$d_1\ge d_2\ge\cdots\ge d_n$、$n=|V(G)|$）のことをいう。非負整数の有限列がグラフ的（graphic）であるとは、それを（並べ替えて）次数列に持つ単純グラフが存在することをいう。
- 多重グラフ $(V,E,\partial)$ の頂点 $v$ の次数とは、$v\in\partial(e)$ となる辺 $e\in E$ の本数のことをいう。すなわち平行辺は重複度込みで数える。ループを許す多重グラフでは、$v$ におけるループ $e$（$\partial(e)=\{v\}$）は $v$ の次数に $2$ を加えるものと約束する。
- 有向グラフ $D=(V,A)$ の頂点 $v$ の出次数（out-degree）$\deg^+_D(v)$ とは $v$ を始点とする有向辺 $(v,w)\in A$ の本数、入次数（in-degree）$\deg^-_D(v)$ とは $v$ を終点とする有向辺 $(u,v)\in A$ の本数のことをいう。ループ $(v,v)$ は出次数と入次数の両方に $1$ ずつ加える。
ループを次数に $2$ 加える約束は、ループが「$v$ を端点として 2 度持つ」辺であることによる。この約束のもとで、次数の総和の公式（thm-degree-handshake）はループを許す多重グラフでもそのまま成り立つ。
直感
次数は、頂点から直接出ている辺の本数を数える局所的な量である。交通網なら交差点に集まる道路の本数、通信網なら機器の直接接続数にあたる。次数 $0$ の頂点は孤立し、次数 $1$ の頂点は 1 本の辺だけでグラフにつながり、次数の大きい頂点は多くの隣接頂点を持つ。1 頂点だけを見て計算できる量であるにもかかわらず、全頂点の次数を集めると辺数（thm-degree-handshake）、正則性、彩色数の上界、Euler閉路の存在などグラフ全体の構造に関する情報が得られる。一方で、次数列が一致しても同型とは限らない（ex-degree-counterexample-same-sequence）ように、次数はグラフの全情報ではない。
例と反例
- 道グラフ $P_n$（$n\ge2$）では、両端の 2 頂点の次数が $1$、残りの $n-2$ 頂点の次数が $2$ である。よって $\delta(P_n)=1$、$\Delta(P_n)=2$、$\overline{d}(P_n)=2(n-1)/n=2-2/n$ であり、次数列は $(2,\dots,2,1,1)$ である。
- 閉路グラフ $C_n$（$n\ge3$）ではすべての頂点の次数が $2$ であり、$C_n$ は $2$-正則である。
- 完全グラフ $K_n$ では各頂点が他の $n-1$ 頂点すべてと隣接するので $\deg(v)=n-1$ であり、$K_n$ は $(n-1)$-正則である。
- 星グラフ $K_{1,n}$（完全二部グラフ）では中心の頂点の次数が $n$、$n$ 個の葉の次数が $1$ である。$\delta=1$、$\Delta=n$、$\overline{d}=2n/(n+1)$ であり、平均次数だけでは中心への辺の集中は読み取れない。
頂点 $1,2,3$ と有向辺 $(1,2),(1,3),(2,3)$ からなる有向グラフでは、$\deg^+(1)=2$、$\deg^+(2)=1$、$\deg^+(3)=0$、$\deg^-(1)=0$、$\deg^-(2)=1$、$\deg^-(3)=2$ である。出次数の総和も入次数の総和も有向辺の本数 $3$ に等しい（prop-degree-directed-sum）。
- 列 $(3,3,1)$ は総和が奇数なので、thm-degree-handshake によりグラフ的でない。
- 列 $(3,3,3,1)$ は総和が $10$ で偶数だが、グラフ的でない。実際、4 頂点のグラフで次数 $3$ の頂点は他の 3 頂点すべてと隣接するので、次数 $3$ の頂点が 3 個あれば残りの頂点はそれら 3 個と隣接し次数が $3$ 以上になり、$1$ にはならない。満たす性質：非負整数の列で、総和が偶数である。満たさない性質：グラフ的である。破る含意：「総和が偶数 ⇒ グラフ的」は成り立たない。thm-degree-havel-hakimi を使えば、$(3,3,3,1)\to(2,2,0)\to(1,-1)$ と負の項が現れることからも判定できる。
性質
次は次数に関する最も基本的な定理であり、握手補題（handshaking lemma）とよばれる（握手補題）。パーティーで各人が握手した回数の総和は握手の回数の 2 倍である、という比喩による名称である。
有限グラフ $G=(V,E)$ について
$$\sum_{v\in V}\deg_G(v)=2|E|$$
が成り立つ。同じ式は、平行辺を重複度込みで数え、ループを $2$ と数える約束（def-degree-multigraph-directed）のもとで、有限な多重グラフおよびループを許す多重グラフでも成り立つ。
頂点と辺の接続する組の集合 $I:=\{(v,e)\in V\times E\mid v\in e\}$ の元の個数を 2 通りに数える。頂点 $v$ を固定すると、$(v,e)\in I$ となる $e$ は $v$ に接続する辺であり、その個数は $\deg_G(v)$ である。よって $|I|=\sum_{v\in V}\deg_G(v)$ である。辺 $e=\{u,v\}$ を固定すると、$(w,e)\in I$ となる $w$ は $e$ の 2 つの端点 $u,v$ に限るので、その個数は $2$ である。よって $|I|=2|E|$ である。両者を等しいとおけば結論を得る。
多重グラフでは、$I$ を $\{(v,e)\mid v\in\partial(e)\}$ とし、ループ $e$（$\partial(e)=\{v\}$）については組 $(v,e)$ を 2 回数えると約束すれば、各頂点についての個数は次数、各辺についての個数は $2$ であり、同じ計算が成り立つ。$\square$
有限グラフにおいて、次数が奇数である頂点の個数は偶数である。特に、次数の総和が奇数である非負整数の列はグラフ的でない。
$V_{\mathrm{odd}}$、$V_{\mathrm{even}}$ をそれぞれ次数が奇数・偶数の頂点全体とすると、thm-degree-handshake により
$$\sum_{v\in V_{\mathrm{odd}}}\deg_G(v)=2|E|-\sum_{v\in V_{\mathrm{even}}}\deg_G(v)$$
であり、右辺は偶数である。左辺は $|V_{\mathrm{odd}}|$ 個の奇数の和だから、その偶奇は $|V_{\mathrm{odd}}|$ の偶奇に一致する。よって $|V_{\mathrm{odd}}|$ は偶数である。$\square$
$n$ 頂点の有限グラフ $G$ の任意の頂点 $v$ について $0\le\deg_G(v)\le n-1$ である。したがって $G$ が空でなければ
$$0\le\delta(G)\le\overline{d}(G)\le\Delta(G)\le n-1$$
であり、また $\overline{d}(G)=2|E(G)|/n$ である。特に $k$-正則な $n$ 頂点グラフの辺数は $kn/2$ であり、$kn$ は偶数である。
単純グラフでは $v$ は自分自身と隣接せず、$N_G(v)\subset V\setminus\{v\}$ だから $0\le\deg_G(v)\le n-1$ である。有限個の実数の平均はそれらの最小値以上、最大値以下なので $\delta(G)\le\overline{d}(G)\le\Delta(G)$ である。$\overline{d}(G)=2|E(G)|/n$ は thm-degree-handshake の両辺を $n$ で割ったものである。$k$-正則なら $\sum_v\deg(v)=kn=2|E|$ である。$\square$
$H$ の辺はすべて $G$ の辺だから $N_H(v)\subset N_G(v)$ であり、個数をとれば $\deg_H(v)\le\deg_G(v)$ である。誘導部分グラフ $G[W]$ の辺は両端点が $W$ に属する $G$ の辺全体なので $N_{G[W]}(v)=N_G(v)\cap W$ である。$W=V\setminus\{u\}$ のとき、$v\in N_G(u)$ なら $N_G(v)\cap W=N_G(v)\setminus\{u\}$ で個数は $1$ 減り、$v\notin N_G(u)$ なら $u\notin N_G(v)$ なので $N_G(v)\cap W=N_G(v)$ である。$\square$
$n$ 頂点の有限グラフ $G$ とその補グラフ $\overline{G}$ について、任意の頂点 $v$ に対し
$$\deg_{\overline{G}}(v)=n-1-\deg_G(v)$$
であり、したがって $\delta(\overline{G})=n-1-\Delta(G)$、$\Delta(\overline{G})=n-1-\delta(G)$ である。
$v$ 以外の各頂点 $u$ は、$uv\in E(G)$ か $uv\in E(\overline{G})$ のちょうど一方を満たす。よって $V\setminus\{v\}$ は $N_G(v)$ と $N_{\overline{G}}(v)$ に分割され、$n-1=\deg_G(v)+\deg_{\overline{G}}(v)$ である。$v$ を動かして最小値・最大値をとれば、$\min_v(n-1-\deg_G(v))=n-1-\max_v\deg_G(v)$ などにより残りの式を得る。$\square$
同型なグラフの対応する頂点は同じ次数を持ち、したがって同型な有限グラフは同じ次数列・最小次数・最大次数・平均次数を持つ（グラフの命題「同型の基本性質」）。逆は成り立たない（ex-degree-counterexample-same-sequence）。
2 個以上の頂点を持つ有限グラフには、次数の等しい 2 頂点が存在する。
$n\ge2$ を頂点数とする。prop-degree-range により各頂点の次数は $\{0,1,\dots,n-1\}$ に属する。次数 $0$ の頂点 $u$ と次数 $n-1$ の頂点 $w$ が同時に存在すると、$w$ は $u$ を含む他のすべての頂点と隣接するので $\deg(u)\ge1$ となり矛盾する。よって次数の値は $\{0,\dots,n-2\}$ または $\{1,\dots,n-1\}$ のいずれか、すなわち高々 $n-1$ 個の値しかとらない。$n$ 個の頂点を $n-1$ 個以下の値に割り当てるので、鳩の巣原理により同じ次数を持つ 2 頂点が存在する。$\square$
有限な有向グラフ $D=(V,A)$ について
$$\sum_{v\in V}\deg^+_D(v)=\sum_{v\in V}\deg^-_D(v)=|A|$$
が成り立つ。
各有向辺 $(u,w)\in A$ は始点 $u$ をちょうど 1 つ持つので、$A$ を始点ごとに分けると $|A|=\sum_{v}|\{(v,w)\in A\}|=\sum_v\deg^+_D(v)$ である。終点についても同様に $|A|=\sum_v\deg^-_D(v)$ である。ループ $(v,v)$ は始点としても終点としても $v$ に 1 回ずつ数えられるので、この議論はループの有無によらない。$\square$
与えられた非負整数の列がグラフ的かどうかは、次の定理により再帰的に判定できる。この定理は Havel（Hav55）と Hakimi（Hak62）によって独立に得られた（Wes01 §1.3）。
$n\ge2$ とし、$d=(d_1,\dots,d_n)$ を $d_1\ge d_2\ge\cdots\ge d_n\ge0$ かつ $d_1\le n-1$ を満たす整数の列とする。$d$ から先頭の項 $d_1$ を取り除き、続く $d_1$ 個の項からそれぞれ $1$ を引いて得られる長さ $n-1$ の列
$$d':=(d_2-1,\ d_3-1,\ \dots,\ d_{d_1+1}-1,\ d_{d_1+2},\ \dots,\ d_n)$$
について、$d$ がグラフ的であることと $d'$ がグラフ的であることは同値である。ただし、負の項を含む列はグラフ的でないと約束する。
$\Delta:=d_1$ とおく。
$d'$ がグラフ的ならば $d$ もグラフ的であること：$d'$ を次数列に持つ $n-1$ 頂点のグラフ $G'$ をとる。$G'$ の頂点と $d'$ の項との間には、各頂点をその次数に等しい項に対応させる 1 対 1 の対応があるので、先頭の $\Delta$ 個の項 $d_2-1,\dots,d_{\Delta+1}-1$ に対応する相異なる頂点を $x_2,\dots,x_{\Delta+1}$ とする（$\deg_{G'}(x_i)=d_i-1$）。新しい頂点 $w$ を加え、$w$ と $x_2,\dots,x_{\Delta+1}$ を結ぶ $\Delta$ 本の辺を加えたグラフを $G$ とすると、$G$ は単純グラフであり、$\deg_G(w)=\Delta=d_1$、$\deg_G(x_i)=d_i$（$2\le i\le\Delta+1$）、その他の頂点の次数は $G'$ におけるものと同じである。よって $G$ の次数列は $d$ である。
$d$ がグラフ的ならば $d'$ もグラフ的であること：$n$ 元集合 $V$、頂点 $w\in V$、および $\Delta$ 元部分集合 $S\subset V\setminus\{w\}$ を固定する（$\Delta\le n-1$ なのでとれる）。さらに写像 $f\colon V\to\mathbb{N}$ を、$f(w)=d_1$、$S$ の上では値 $d_2,\dots,d_{\Delta+1}$ を 1 つずつとり、$V\setminus(S\cup\{w\})$ の上では残りの値 $d_{\Delta+2},\dots,d_n$ を 1 つずつとるように定める。$d$ はグラフ的なので、頂点の名前を付け替えることにより、$V$ 上のグラフ $G$ で任意の $v\in V$ について $\deg_G(v)=f(v)$ となるものが存在する。このような $G$ では、$x\in S$、$z\in V\setminus(S\cup\{w\})$ ならば $\deg_G(x)\ge\deg_G(z)$ である。
まず、$\deg_G=f$ かつ $N_G(w)=S$ となる $G$ が存在することを示す。$\deg_G=f$ を満たす $V$ 上のグラフ $G$ を、$|N_G(w)\cap S|$ が最大になるように選ぶ。$N_G(w)\neq S$ と仮定する。$|N_G(w)|=\Delta=|S|$ だから、$x\in S\setminus N_G(w)$ と $z\in N_G(w)\setminus S$ が存在する。$z\neq w$ かつ $z\notin S$ なので $\deg(x)\ge\deg(z)$ である。ここで $N_G(x)$ の元 $y$ で、$y\neq z$ かつ $yz\notin E(G)$ となるものが存在することを示す。$w\notin N_G(x)$、$w\in N_G(z)$ に注意すると、$N_G(x)\cap(N_G(z)\cup\{z\})\subset(N_G(z)\setminus\{w\})\cup\{z\}$ であり、右辺の元の個数は $\deg(z)\le\deg(x)=|N_G(x)|$ である。もし $N_G(x)\subset(N_G(z)\setminus\{w\})\cup\{z\}$ ならば、個数の比較から $N_G(x)=(N_G(z)\setminus\{w\})\cup\{z\}$ となり、$z\in N_G(x)$、すなわち $x\in N_G(z)\setminus\{w\}\subset N_G(x)$ となって $x\notin N_G(x)$ に反する。よって $y\in N_G(x)$ で $y\notin N_G(z)\cup\{z\}$ となるものが存在し、$y\neq w$ でもある。
このとき、$G$ から辺 $xy$、$wz$ を取り除き、辺 $wx$、$yz$ を加えたグラフを $G_1$ とする。$wx\notin E(G)$、$yz\notin E(G)$、$w\neq x$、$y\neq z$ なので $G_1$ は単純グラフであり、$x$ は $y$ を失って $w$ を得、$y$ は $x$ を失って $z$ を得、$z$ は $w$ を失って $y$ を得、$w$ は $z$ を失って $x$ を得るので、すべての頂点の次数は変わらない。よって $G_1$ も $\deg_{G_1}=f$ を満たし、$N_{G_1}(w)=(N_G(w)\setminus\{z\})\cup\{x\}$ だから $|N_{G_1}(w)\cap S|=|N_G(w)\cap S|+1$ となって $G$ の選び方に反する。ゆえに $N_G(w)=S$ である。
$\deg_G=f$ かつ $N_G(w)=S$ である $G$ をとり、$G$ から $w$ とそれに接続する辺を取り除いたグラフ $G-w$ を考える。prop-degree-subgraph-monotonicity により、$S$ の各頂点の次数はちょうど $1$ 減り、他の頂点の次数は変わらない。よって $G-w$ の次数列は $d'$ を並べ替えたものであり、$d'$ はグラフ的である。$\square$
Havel-Hakimi の定理を、各段で非増加順に並べ替えてから再び適用し、これを繰り返せば、列が「すべて $0$ の列」に到達するか、負の項が現れるか（または $d_1\le n-1$ が破れるか）によってグラフ的かどうかを有限回の計算で判定できる。前者の場合には証明の前半の構成を逆にたどってグラフを実際に構成できる。
グラフ的であることの、再帰によらない特徴付けとして次が知られている。
非負整数の列 $d_1\ge d_2\ge\cdots\ge d_n$ がグラフ的であるための必要十分条件は、$\sum_{i=1}^nd_i$ が偶数であり、かつ各 $k=1,\dots,n$ について
$$\sum_{i=1}^{k}d_i\le k(k-1)+\sum_{i=k+1}^{n}\min\{d_i,k\}$$
が成り立つことである。
補足
次数は多くの定理の仮定や結論に現れる。頂点数 $n\ge3$ のグラフで最小次数 $\delta(G)\ge n/2$ を仮定すると Hamilton閉路が存在し（Diracの定理、Die17 §10.1）、最大次数 $\Delta(G)$ は彩色数の上界 $\Delta(G)+1$ を与え、連結グラフでは完全グラフと奇閉路を除いて $\Delta(G)$ 自身が上界になる（Brooksの定理、Die17 §5.2）。すべての頂点の次数が偶数であることは、連結グラフが Euler 閉路を持つための必要十分条件である（Euler閉路、Die17 §1.8）。正則グラフの存在条件・例は 正則グラフ、次数列のより詳しい理論は 次数列 を参照する。本記事の記述はおおむね Die17 §1.2 および Wes01 §1.3 に従い、平均次数の記法と多重グラフの流儀については Bol02 第 I 章も参照した。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
