Erdős–Gallaiの定理(Erdős–Gallai theorem)とは、$0$ 以上の整数の列 $d_1\ge\dots\ge d_n$ が単純グラフの次数の列であるための必要十分条件は、総和が偶数で、すべての $k=1,\dots,n$ について $\sum_{i\le k}d_i\le k(k-1)+\sum_{i>k}\min(d_i,k)$ が成り立つことである、という定理である。不等式は次数の大きい $k$ 頂点の次数の和を数えたもので、ほかに障害がないことが定理の中身である。調べる $k$ は $d_k\ge k$ かつ $d_k>d_{k+1}$ のものに絞れる。
Erdős–Gallaiの定理(Erdős–Gallai theorem)は、$0$ 以上の整数の列 $d_1\ge\dots\ge d_n$ が単純グラフの次数の列になるための必要十分条件を、不等式だけで与える定理である。条件は、総和が偶数であることと、すべての $k=1,\dots,n$ について
$$
\sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}^n\min(d_i,k)
$$
が成り立つことである。
左辺は次数の大きい $k$ 頂点の次数の和である。この和は、$k$ 頂点どうしの辺から高々 $k(k-1)$、残りの頂点 $v_i$ からは高々 $\min(d_i,k)$ しか受け取れない。不等式はこの数え上げを書いただけなので、必要性はすぐに分かる。定理の中身は、これ以外に障害がない という十分性である。
判定の方法としては、頂点を 1 つずつ消していく再帰的な方法(次数(グラフ) の定理「次数列の再帰的判定(Havel-Hakimi)」)もある。Erdős–Gallai の条件は、再帰を使わず、列を見るだけで判定でき、さらに実現できないときには「どの $k$ 頂点が入りきらないか」を示す。二部グラフの場合の対応物が Gale–Ryserの定理 である。定理は EG60 による。
| 主張 | 内容 | この記事で |
|---|---|---|
| thm-eg-main | 列がグラフ的であることの判定 | 証明する |
| prop-eg-reduce | 調べる $k$ を絞る | 証明する |
| cor-eg-conj | 共役による書き換え | 証明する |
| prop-eg-unique | すべて等号のとき実現はただ 1 つ | 証明する |
この記事のグラフは、ループと多重辺のない有限グラフ(単純グラフ)とする。頂点 $v$ の次数を $\deg v$、隣接する頂点の集合を $N(v)$ と書く。$u$ と $v$ が隣接しないことを $u\not\sim v$ と書く。
$0$ 以上の整数の列 $d=(d_1,\dots,d_n)$ が グラフ的(graphic)であるとは、頂点 $v_1,\dots,v_n$ の単純グラフ $G$ で、すべての $i$ について $\deg v_i=d_i$ となるものがあることをいう。この $G$ を $d$ の 実現 という。
列の順番を入れ替えても頂点の名前が変わるだけなので、$d_1\ge\dots\ge d_n$ としてよい。広義単調減少の列 $d$ と $0\le k\le n$ について、
$$
f(k):=k(k-1)+\sum_{i=k+1}^n\min(d_i,k)-\sum_{i=1}^kd_i
$$
とおく。$f(0)=0$ である。
$d_1\ge\dots\ge d_n\ge0$ を整数とする。$d$ がグラフ的であるための必要十分条件は、$\sum_id_i$ が偶数で、すべての $k=1,\dots,n$ について $f(k)\ge0$ であることである。
必要性は数え上げで、十分性は辺をつなぎ替えてグラフを少しずつ目標に近づける。証明は次の節の prf-eg-main で与える。
次の言葉を使う。
頂点 $v_1,\dots,v_n$ の単純グラフ $G$ で、すべての $i$ について $\deg v_i\le d_i$ であるものを $d$ の 部分実現 という。$d_i-\deg v_i$ を $v_i$ の 不足 といい、不足が正の頂点を 足りない頂点 という。
必要性. $G$ を実現とする。握手補題 により総和は偶数である。$S:=\{v_1,\dots,v_k\}$ とする。$S$ の次数の和は、$S$ の内部の辺を 2 回、$S$ と外を結ぶ辺を 1 回ずつ数える。内部の辺は高々 $k(k-1)/2$ 本で、外の頂点 $v_i$ から $S$ への辺は $k$ 本以下かつ $d_i$ 本以下である。よって $f(k)\ge0$ である。
十分性. 総和が偶数で、すべての $k$ で $f(k)\ge0$ とする。空グラフは部分実現である。部分実現が実現でないとき、次数の組 $(\deg v_1,\dots,\deg v_n)$ を辞書式順序で真に大きくする部分実現が作れることを示す。頂点数を固定したグラフは有限個なので、これを繰り返すと実現に達する。
$G$ を実現でない部分実現とし、足りない頂点のうち番号が最小のものを $x=v_r$ とする。$A:=\{v_1,\dots,v_{r-1}\}$、$B:=\{v_{r+1},\dots,v_n\}$ とおく。$A$ の頂点の不足は $0$ である。$\sum_id_i$ と $\sum_i\deg v_i$ はともに偶数なので不足の総和は偶数であり、
($\ast$) $x$ の不足が $1$ なら、$B$ に足りない頂点がある。
また、$a\in A$ なら $d_a\ge d_r>\deg x$ である。以下の改良では、$A$ の頂点の次数を変えず、$x$ の次数を増やし、$B$ の頂点の次数は $d$ を超えない範囲で変えるだけである。よって辞書式順序で真に大きくなる。$U:=\{v\ne x\mid v\not\sim x\}$ とおく。
改良 1. $z\in B$ が足りない頂点で $z\not\sim x$ なら、辺 $xz$ を足す。
改良 2. $u\in U$ が $w\in B$ と隣接するなら、辺 $uw$ を除いて辺 $ux$ を足す($w$ の次数だけが $1$ 減る)。
これらが使えないとき、$U$ の各頂点の隣接点はすべて $A$ にあり、$U\cap B$ の頂点は足りなくない。
改良 3. $u\in A\cap U$ があるとする。$\deg u>\deg x$ で $u\not\sim x$ なので、$N(u)$ は $N(x)$ に含まれず、$w\in N(u)\setminus N(x)$ がある。$w\ne x$ なので $w\in U$ で、改良 2 が使えないから $w\in A$ である。$x$ の不足が $2$ 以上なら、辺 $uw$ を除いて辺 $xu,xw$ を足す。不足が $1$ なら ($\ast$) により $B$ に足りない頂点 $y$ があり、改良 1 が使えないので $y\sim x$ である。$w$ の隣接点は $A$ にあるので $y\not\sim w$ である($w\in U$)。辺 $uw$ を除いて辺 $xu,wy$ を足す。
これも使えないとき、$A\subset N(x)$ で、$U\subset B$ である。
改良 4. $a\in A$ と $z\in N(x)$ が $z\ne a$、$z\not\sim a$ を満たすとする。$N(a)$ は $\{x\}$、$N(x)\setminus\{a,z\}$、$U$ の和に含まれる。$\lvert N(a)\rvert\ge\lvert N(x)\rvert+1$ なので、$\lvert N(a)\cap U\rvert\ge2$ である。$p\in N(a)\cap U$ をとる。次のどれかが当てはまれば改良できる。
どの改良も使えない場合. このような $G$ は存在しないことを示す。$A':=A\cup\{x\}$ とする。改良 3 と改良 4 の第 2 の場合が使えないので、$A'$ は $r$ 頂点の完全グラフをなす。$v\in B$ について、$A'$ の中の隣接点の個数 $e(v)$ を調べる。
$d=(2,2,2,2)$ とする。$v_1$ に対して改良 1 を 2 回使い、辺 $v_1v_2,v_1v_3$ を足す。$v_2$ に対して辺 $v_2v_3$ を足す。三角形ができ、足りない頂点は $x=v_4$(不足 $2$)だけである。$A=\{v_1,v_2,v_3\}$、$B=\emptyset$ である。改良 3 で $u=v_1,w=v_2$ とし、辺 $v_1v_2$ を除いて辺 $v_4v_1,v_4v_2$ を足す。閉路 $v_1v_3v_2v_4$ が得られる。
| $d$ | 総和 | $f(1),f(2),\dots$ | 判定 |
|---|---|---|---|
| $(3,3,2,2,2)$ | $12$ | $1,2,2,4,8$ | グラフ的 |
| $(4,4,3,2,2,1)$ | $16$ | $1,1,0,2,6,14$ | グラフ的 |
| $(3,2,2,1)$ | $8$ | $0,0,0,4$ | グラフ的(ex-eg-threshold) |
| $(3,3,1,1)$ | $8$ | $0,-2,0,4$ | $f(2)< 0$ でグラフ的でない |
$(3,3,1,1)$ では、次数 $3$ の 2 頂点は残りの全頂点と隣接するので、残りの 2 頂点の次数は $2$ 以上でなければならない。$k=2$ の不等式はこのことである。thm-eg-main と次の節の判定は、頂点数 $6$ 以下で全グラフの次数の列と一致し、証明の手順は頂点数 $9$ 以下で条件を満たすすべての列に実現を作ることを確かめた。
$n$ 個の不等式の全部は要らない。$d$ の 共役 $c_j:=\#\{i\mid d_i\ge j\}$ と、$s:=\#\{k\mid d_k\ge k\}$ を使う。$d_k\ge k$ は $k\le s$ と同値である($d_k$ は減少し $k$ は増加する)。$d_{n+1}:=-1$ と約束する。
$d_1\ge\dots\ge d_n\ge0$ とする。
1:定義から、$d_i\ge k$ のとき $\min(d_i,k)-\min(d_i,k-1)=1$、それ以外で $0$ なので
$$
f(k)-f(k-1)=2(k-1)+\#\{i>k\mid d_i\ge k\}-\min(d_k,k-1)-d_k
$$
である。$k\le s$ なら $d_1,\dots,d_k\ge k$ なので $\#\{i>k\mid d_i\ge k\}=c_k-k$ であり、$\min(d_k,k-1)=k-1$ である。これで第 1 の式を得る。$k>s$ なら $d_k\le k-1$ で、$i>k$ に対して $d_i\le k-1$ なので、第 1 項と最後の 2 項だけが残り、第 2 の式を得る。
2:片方向は明らかである。逆を示す。1 の第 2 の式から $k\ge s$ では $f(k)\ge f(s)$ なので、$k\le s$ を調べればよい。$\{1,\dots,s\}$ を $d$ の値が等しい段に分ける。1 段を $m< k\le l$ とする($d_{m+1}=\dots=d_l$、$d_m>d_{m+1}$ または $m=0$)。この段の上で $d_k$ は一定で $c_k$ は広義減少なので、差分 $f(k)-f(k-1)$ は広義減少である。すなわち $f$ は段の上で凹である。
$l< s$ または $d_s>d_{s+1}$ なら、$f(m)$ と $f(l)$ はともに調べる値(または $f(0)=0$)なので、凹性から段の上で $f\ge0$ である。残りは $l=s$ で $d_s=d_{s+1}$ の場合である。このとき $s+1\le n$ で、$d_{s+1}< s+1$ と $d_s\ge s$ から $d_s=d_{s+1}=s$ である。$c_s\ge s+1$ なので、最後の差分 $c_s-1-d_s$ は $0$ 以上で、広義減少性からこの段のすべての差分が $0$ 以上である。よって段の上で $f\ge f(m)\ge0$ である。$\square$
絞り込みの条件 $d_k>d_{k+1}$、$d_k\ge k$ は TV03 によるものとして TT08 p. 3515 に紹介されている。prop-eg-reduce の 1 は、$f$ を次の形に書き直すことでもある。
$\sum_id_i$ が偶数の列 $d_1\ge\dots\ge d_n\ge0$ がグラフ的であることと、すべての $k=1,\dots,s$ について
$$
\sum_{i=1}^k(d_i+1)\le\sum_{i=1}^kc_i
$$
であることは同値である。
$f(0)=0$ と prop-eg-reduce の 1 を $k\le s$ で足すと $f(k)=\sum_{i\le k}(c_i-1-d_i)$ である。不等式は $f(k)\ge0$ と同じである。prop-eg-reduce の 2 と thm-eg-main から従う。$\square$
Gale–Ryserの定理 の条件は「行和 $r$ が列和の共役に優越される」で、部分和 $\sum_{i\le k}r_i\le\sum_{i\le k}c^*_i$ の形である。上の不等式は、左辺に $+1$ が付くところだけが違う。これは対角成分が $0$ であることの効果である。実現 $G$ の隣接行列は、対称で対角が $0$、行和も列和も $d$ の $0$-$1$ 行列であり、対角の箱が使えない分だけ各 $k$ で $k$ 個ずつ条件が厳しくなる。たとえば $d=(1,1,1)$ は $3\times3$ の置換行列を行和・列和 $d$ の行列としてもつので Gale–Ryser の条件を満たすが、総和が奇数でグラフ的でない。また $d=(2,1,1,0)$ は($s=1$、$c_1=3$)$3\le3$ を満たしグラフ的である。
$d_1\ge\dots\ge d_n\ge0$ がグラフ的で、すべての $k=1,\dots,s$ で $f(k)=0$ とする。このとき頂点に番号を付けた実現はただ 1 つで、それは次で与えられる:$j< i$ について、$j\le s$ かつ $d_i\ge j$ のときに限り $v_j$ と $v_i$ を結ぶ。
$G$ を実現とする。$k\le s$ で $f(k)=0$ なので、thm-eg-main の必要性の評価はすべて等号である。すなわち $\{v_1,\dots,v_k\}$ は完全グラフをなし、$i>k$ の $v_i$ はこの中に $\min(d_i,k)$ 個の隣接点をもつ。したがって次が成り立つ。
(a) $i>k$、$d_i\ge k$ なら、$v_i$ は $v_1,\dots,v_k$ のすべてと隣接する。(b) $i>k$、$d_i< k$ なら、$v_i$ の隣接点はすべて $v_1,\dots,v_k$ の中にある。(a) は $k=0$ でも自明に成り立つ。
$j\le s$、$j< i$ とする。$d_i\ge j$ なら $k=j$ の (a) により $v_j\sim v_i$ である。$d_i< j$ なら $k=j-1$ を考える。$i>k$ である。$d_i=j-1$ なら (a) により $v_i$ は $v_1,\dots,v_{j-1}$ で次数を使い切るので $v_j\not\sim v_i$ である。$d_i< j-1$ なら (b) により $v_j\not\sim v_i$ である。
$s< j< i$ とする。$d_i\le d_{s+1}\le s$ なので、$k=s$ の (a)・(b) により $v_i$ の隣接点はすべて $v_1,\dots,v_s$ の中にあり、$v_j\not\sim v_i$ である。以上で $G$ の辺がすべて決まる。$\square$
$d=(3,2,2,1)$ では $s=2$、$c=(4,3,1)$ で、$f(1)=4-1-3=0$、$f(2)=0+3-1-2=0$ である。実現は $v_1$ を $v_2,v_3,v_4$ と、$v_2$ を $v_3$ と結んだものだけである。
$d=(2,2,2,2)$ では $s=2$、$c=(4,4)$ で $f(1)=1>0$ であり、実現は長さ $4$ の閉路で、番号の付け方が $3$ 通りある。$d=(1,1,1,1)$ では $f(1)=2>0$ で、完全マッチングが $3$ 通りある。
| 外す条件 | 反例 | 成り立たなくなるもの |
|---|---|---|
| 総和が偶数 | $(1,1,1)$:$f(1),f(2),f(3)$ は $1,1,3$ で不等式はすべて成り立つが、総和が奇数 | 「不等式だけでグラフ的」は偽 |
| 列を大きい順に並べる | $(1,1,3,3)$:並べ替えずに計算すると和は偶数で $f(k)\ge0$($k=1,\dots,4$ で $2,4,4,4$)だが、$(3,3,1,1)$ はグラフ的でない | 並べずに判定すること |
| 小さい $k$ だけ調べる | $(3,3,1,1)$:$f(1)=0$ だが $f(2)=-2$ | $k=1$ だけの条件 $d_1\le\#\{i>1\mid d_i\ge1\}$ では足りない |
| 単純グラフ | $(3,3)$:2 頂点を辺 3 本で結んだ 多重グラフ の次数の列だが、$f(1)=1-3< 0$ | 多重辺を許すと条件はもっと弱くなる(多重グラフ の記事の次数列の節) |
Havel–Hakimi との違い. 再帰的な判定は実現を作りながら進むが、途中で列を何度も並べ直す。Erdős–Gallai の判定は、並べ替えのあと $c_j$ と部分和を一度計算すれば $s$ 個以内の不等式を調べるだけで済む。一方、実現が必要なら、prf-eg-main の改良の手順か、再帰的な判定を使う。
実現できないときの証拠. $f(k)< 0$ となる $k$ があれば、大きい $k$ 頂点は残りの頂点から受け取れる辺だけでは次数を満たせない。不等式が成り立たないことは実現がないことの短い証拠になる。
実現の連結性などは別の問題. 定理は実現の存在だけを述べる。実現が連結かどうか、彩色数がいくつかなどは、同じ列の実現でも変わる。ex-eg-threshold の $(2,2,2,2)$ の実現は連結だが、$(2,2,2,2,2,2)$ は長さ $6$ の閉路にも三角形 2 つにもなる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する