Erdős–Gallaiの定理

同義語:Erdős-Gallaiの定理Erdos–Gallaiの定理Erdős–Gallai theorem

概要

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}$ のものに絞れる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 単純グラフ, 次数(グラフ), 握手補題

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$ である。

Erdős–Gallai の定理

$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$ をとる。次のどれかが当てはまれば改良できる。

  • $z$ が足りない頂点(このとき $z\in B$):辺 $ap$ を除いて辺 $az,xp$ を足す。$a,p$ の次数は変わらず、$x,z$ の次数が $1$ 増える。
  • $z\in A$:$a$ と同じ理由で $\lvert N(z)\cap U\rvert\ge2$ なので、$t\in N(z)\cap U$ で $t\ne p$ のものがある。辺 $ap,zt$ を除いて辺 $az,xp$ を足す。$x$ の次数が $1$ 増え、$t\in B$ の次数が $1$ 減り、ほかは変わらない。
  • $z\in B$ で、$z$ が $t\in B$ と隣接する:$U$ の頂点の隣接点は $A$ にあるので $t\notin U$、とくに $t\ne p$ である。辺 $ap,zt$ を除いて辺 $az,xp$ を足す。$x$ の次数が $1$ 増え、$t$ の次数が $1$ 減り、ほかは変わらない。

どの改良も使えない場合. このような $G$ は存在しないことを示す。$A':=A\cup\{x\}$ とする。改良 3 と改良 4 の第 2 の場合が使えないので、$A'$ は $r$ 頂点の完全グラフをなす。$v\in B$ について、$A'$ の中の隣接点の個数 $e(v)$ を調べる。

  • $v\in U$:隣接点はすべて $A$ にあり、足りなくないので、$e(v)=d_v\le r-1$ である。
  • $v\in N(x)$ で $A'$ の全部と隣接する:$e(v)=r$ で $d_v\ge r$ である。
  • $v\in N(x)$ で、ある $a\in A$ と隣接しない:改良 4 が使えないので、足りなくなく、隣接点はすべて $A'$ にある。よって $e(v)=d_v\le r-1$ である。
    どの場合も $e(v)=\min(d_v,r)$ である。したがって、$x$ の不足を $\delta>0$ として
    $$ \sum_{i=1}^rd_i=\delta+\sum_{i=1}^r\deg v_i=\delta+r(r-1)+\sum_{i>r}\min(d_i,r) $$
    となり、$f(r)=-\delta< 0$ である。これは仮定に反する。$\square$
証明の出所

$f$ の不等式を使うのは最後の 1 回の $k=r$ だけである。短い構成的な証明としては TVW10 がある。上の 4 つの改良はこの記事の整理である。別の短い証明は TT08 にあり、Havel–Hakimi 型の操作を繰り返して不等式と結びつける。

手順の実行

$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$ 以下で条件を満たすすべての列に実現を作ることを確かめた。

調べる $k$ を減らす

$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. $1\le k\le s$ なら $f(k)-f(k-1)=c_k-1-d_k$ である。$k>s$ なら $f(k)-f(k-1)=2(k-1-d_k)\ge0$ である。
  2. すべての $k$ で $f(k)\ge0$ であることと、$k\le s$ かつ $d_k>d_{k+1}$ である $k$ のすべてで $f(k)\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$ を満たしグラフ的である。

等号の場合

すべて等号なら実現はただ 1 つ

$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 つにもなる。

関連項目

参考文献

[1]
Paul Erdős, Tibor Gallai, Gráfok előírt fokszámú pontokkal, Matematikai Lapok, 1960, pp. 264–274
[2]
Amitabha Tripathi, Sushmita Venugopalan, Douglas B. West, A short constructive proof of the Erdős–Gallai characterization of graphic lists, Discrete Mathematics, 2010, pp. 843–844
[3]
Amitabha Tripathi, Himanshu Tyagi, A simple criterion on degree sequences of graphs, Discrete Applied Mathematics, 2008, pp. 3513–3517、§2
[4]
Amitabha Tripathi, Sujith Vijay, A note on a theorem of Erdős & Gallai, Discrete Mathematics, 2003, pp. 417–420

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する