1. 概要

単純無向グラフにおいて，各頂点の次数を並べてできる列 $d = (\deg(1),\deg(2),\ldots,\deg(n))$ を次数列といいます．

本記事では，$d=(d_1,d_2,\ldots,d_n)$ が単純無向グラフの次数列となるための必要十分条件を与える $\text{Erd\H{o}s--Gallai}$ の定理および，そのような単純無向グラフを実際に構成するHavel–Hakimi アルゴリズムを解説します．

なお，文字表示の都合により記事タイトルや見出しでは「$\text{Erd\H{o}s--Gallai}$ の定理」を「Erdos–Gallai の定理」とも表記します（両者は同一です）．

2. 前提知識

本記事を理解するためには，単純無向グラフやグラフの次数などの用語を理解していれば十分です．

3. 次数列

本記事において，$n$ は正整数であるとし，無向グラフといえば，頂点に $1$ から $n$ までの番号が付いた $n$ 頂点の無向グラフのことであるとします．

【定義 1】（次数列）
無向グラフにおいて，各頂点の次数を並べてできる列 $$d = (\deg(1),\deg(2),\ldots,\deg(n))$$ を次数列（degree sequence）という．

次の握手補題は次数列に関する基本的な性質です．

【補題 2】（握手補題）
辺の個数が $m$ であるような無向グラフにおいて，頂点の次数の総和 $\sum_{i=1}^n\deg(i)=2m$ である．特に次数列の総和は偶数である．

証明は簡単です．グラフにひとつ辺を追加したときに，頂点の次数の総和が $2$ 増えることを示せばよいです．これは，辺の両端点の次数が $1$ ずつ増える（辺がループである場合にはある $1$ 頂点の次数が $2$ 増える）ことから分かります．

ループのある場合の次数の定義に注意してください（グラフ理論用語集参照）．$\blacksquare$

本記事では，列 $d$ を与えたときに $d$ を次数列とするグラフをひとつ見つけるという問題について考えます．特に，単純無向グラフの場合について考えます．

次は，具体的な例で考えてみたい方向けの問題です．

【問題 3】

次数列が $(4,4,3,2,2,1)$ であるような単純無向グラフは存在しますか？
次数列が $(4,3,3,2,2,1)$ であるような単純無向グラフは存在しますか？
次数列が $(4,4,4,2,1,1)$ であるような単純無向グラフは存在しますか？
$n$ を正整数とするとき，$n$ 頂点の単純無向グラフであって，すべての頂点の次数が相異なるものは存在しますか？

解答

存在します．グラフの具体例については省略します．もし手作業で見つけられなかった場合には，「5. Havel–Hakimi アルゴリズム」を読んだ後に再挑戦してください．
存在しません．握手補題から証明できます．
存在しません．証明は省略しますが，もし証明ができなかった場合には，「4.2. 必要性の証明」を読んだ後に再挑戦してください．
$n=1$ ならば存在し，$n\geq 2$ ならば存在しません．$n=1$ の場合は明らかです．$n\geq 2$ の場合の証明は以下の通りです．次数は $0$ 以上 $n-1$ 以下の整数なので，次数 $0,1,\ldots,n-1$ の頂点がすべて存在する必要があります．一方で $n\geq 2$ ならば次数 $0$ の頂点と次数 $n-1$ の頂点が同時に存在できないことは簡単に分かります．

4. Erdos–Gallai の定理

4.1. 定理の主張

$\text{Erd\H{o}s--Gallai}$ の定理は，非負整数列が単純無向グラフの次数列となるための必要十分条件を与えるものです．なお，非負整数列に対するソートは明らかに単純無向グラフの存在判定に影響しないため，次数列が広義単調減少である場合を扱っています．

【定理 4】（$\text{Erd\H{o}s--Gallai}$ の定理）

非負整数からなる広義単調減少列 $d=(d_1,d_2,\ldots,d_n)$ について，$d$ がある単純無向グラフの次数列であることと，次の $2$ 条件が成り立つことは同値である：

$\sum_{i=1}^n d_i$ が偶数である．
任意の $k=1,2,\ldots,n$ について次が成り立つ：

$$ \sum_{i=1}^k d_i \le k(k-1)+\sum_{i=k+1}^n \min(d_i,k). $$

4.2. 必要性の証明

必要性を証明します．つまり非負整数からなる広義単調減少列 $d=(d_1,d_2,\ldots,d_n)$ について，【定理 4】の $2$ 条件が成り立つことを証明します．$\sum_{i=1}^n d_i$ が偶数であることは，握手補題から明らかです．

次数列 $d$ について $\sum _ {i=1} ^ k d_i \leq k(k-1) + \sum _ {i=k+1} ^ n \min(d_i,k)$ を示します．$k$ を固定します．

頂点 $1, 2, \ldots, k$ の間を結ぶ辺の個数を $a$，
頂点 $1, 2, \ldots, k$ と，頂点 $k+1,k+2,\ldots,n$ の間を結ぶ辺の個数を $b$

とすれば，$\sum_{i=1}^k d_i=2a+b$ が成り立ちます．この右辺を上から評価しましょう．

まず，$a\leq \binom{k}{2}=\frac{1}{2}k(k-1)$ です．$1, 2, \ldots, k$ のすべての $2$ 点組の間に辺がある場合が上界です．

次に，$b$ について考えます．$k+1\leq i$ を固定すると，$k$ 以下の番号の頂点と $i$ を結ぶ辺の個数は $\min(d_i,k)$ 以下です．これを足し合わせることで $b\leq \sum_{i=k+1}^n \min(d_i,k)$ が分かります．

$a,b$ に対する上からの評価を足し合わせることで，必要性が示されました． $\blacksquare$

4.3. 十分性の証明

本節において，非負整数からなる広義単調減少列 $d=(d_1,d_2,\ldots,d_n)$ であって，【定理 4】の条件

$\sum_{i=1}^n d_i$ が偶数である．
任意の $k=1,2,\ldots,n$ について次が成り立つ：

$$ \sum_{i=1}^k d_i \le k(k-1)+\sum_{i=k+1}^n \min(d_i,k). $$

を満たすものを固定します．グラフといえば頂点 $1,2,\ldots,n$ を持つ単純無向グラフを指すものとし，グラフ $G$ における頂点 $i$ の次数を $d_G(i)$ と書くことにします．

目標は，任意の $i$ について $d_G(i)=d_i$ を満たすような $G$ の存在証明です．そのためには次の補題を示せば十分です．

【補題 5】

グラフ $G$ および，整数 $r$ （$1\leq r\leq n$）について，以下の条件が成り立つとする．

$1\leq i < r$ に対して $d_G(i)=d_i$．
$d_G(r) < d_r$．
$r < i\leq n$ に対して $d_G(i)\leq d_i$．

このとき，グラフ $G'$ であって以下の条件を満たすものが存在する．

$1\leq i < r$ に対して $d_{G'}(i)=d_i$．
$d_G(r) < d_{G'}(r)\leq d_r$．
$r < i\leq n$ に対して $d_{G'}(i)\leq d_i$．

まず，$G$ に頂点 $r+1,r+2,\ldots,n$ の間を結ぶ辺があれば削除しておきます．この操作は $d_G(1)\ldots,d_G(r)$ を変えません．よって以下では，$\lbrace r+1,r+2,\ldots,n\rbrace$ が独立集合であることを仮定します．

また，各 $1\leq i<r$ に対して $d_G(i)=d_i\geq d_r>d_G(r)$ より，$i$ と隣接し，$r$ とは隣接しないような頂点 $u$ （$u\neq i, r$）が存在します．この $u$ を $u_i$ と書くことにします．

4.2 の証明と同様に，$G$ において

頂点 $1, 2, \ldots, r$ の間を結ぶ辺の個数を $a$，
頂点 $1, 2, \ldots, r$ と，頂点 $r+1,r+2,\ldots,n$ の間を結ぶ辺の個数を $b$

とすれば，$\sum_{i=1}^r d_G(i)=2a+b$ が成り立ちます．よって

$$ 2a+b = \sum _ {i=1} ^ r d_G(i) < \sum_{i=1} ^ r d_i \leq r(r-1) + \sum _ {i=r+1} ^ n\min(r,d_i) $$

が成り立ちます．したがって，$a<\frac{r(r-1)}{2}$ または $b<\sum_{i=r+1}^n\min(r,d_i)$ が成り立ちます．

前者の場合には頂点 $1,2,\ldots,r$ のうちある $2$ 頂点の間に辺が存在しません．後者の場合には，$\lbrace r+1,r+2,\ldots,n\rbrace$ が独立集合であることから $b=\sum_{i=r+1}\deg_G(i)$ なので，ある $k$（$r+1\leq k$）について $\deg_G(k)<\min(r,d_k)$ が成り立ちます．

前者の場合をさらに (1), (2) に分けることで，次のように場合分けをします．

(1)：ある $i$（$1\leq i < r$）について，$G$ に辺 $ir$ が存在しない場合．
(2)：ある $i,j$（$1\leq i < j < r$）について，$G$ に辺 $ij$ が存在しない場合．
(3)：ある $k$（$r+1\leq k$）について $\deg_G(k)<\min(r,d_k)$ が成り立つ場合

(1) の場合

まず，$d_G(r)\leq d_r-2$ であるならば，$G$ から辺 $iu_i$ を削除して辺 $ir, u_ir$ を追加したものを $G'$ とすればよいです（$r$ の次数が $2$ 増加することから $d_G(r)\leq d_r-2$ が必要となります）．

次に，$d_G(r)= d_r-1$ であるとします．握手補題より $\sum _ {i = 1} ^ n d _ G(i)$ は偶数で，仮定より $\sum _ {i=1} ^ n d _ i$ も偶数なので $d_G(k)\leq d_k-1$ となる $k$（$k\neq r$）が存在します．$i<r$ について $d_G(i)=d_i$ なので，$r<k$ です．

$G$ において辺 $rk$ が存在しないならば，$G$ に辺 $rk$ を追加したものを $G'$ とすればよいです．辺 $rk$ が存在するならば，$G$ から辺 $iu_i, rk$ を削除して辺 $ir, u_ir$ を追加したものを $G'$ とすればよいです．

(2) の場合

辺 $ir, jr$ が存在しない場合は (1) として処理できるため，辺 $ir, jr$ は存在するとしてよいです． $u_i, u_j < r$ の場合は (1) として処理できるため，$r < u_i,u_j$ としてよいです．

$G$ から辺 $iu_i,ju_j$ を削除し，辺 $ij,u_jr$ を追加したものを $G'$ とすればよいです．なお $u_i=u_j$ であることはありえますが証明に影響はありません．

(3) の場合

$r$ と $k$ が隣接していないならば，$G$ に辺 $rk$ を追加したものを $G'$ とすればよいです（(3) の仮定より $d_G(k)<d_k$ であることに注意してください）．

$r$ と $k$ が隣接しているとします．$d_G(k)<r$ より，ある $i$ （$1\leq i<r$）であって $k$ と隣接しないものが存在します．この場合には，$G$ から $iu_i$ を削除し，$ik, u_ir$ を追加したものを $G'$ とすればよいです．

5. Havel–Hakimi アルゴリズム

$d=(d_1,d_2,\ldots,d_n)$ が【定理 4】の条件を満たすときに，実際に $d$ を次数列に持つようなグラフをひとつ構成することを考えてみましょう．

ひとつの方法として，4.3 節の証明をたどるものがありますが，より簡潔な貪欲アルゴリズムにより目的を達成できることが証明できます．

【定理 6】

非負整数からなる広義単調減少列 $d=(d_1,d_2,\ldots,d_n)$ が，単純無向グラフ $G$ の次数列であるとする．

このとき，同じ次数列を持つ単純無向グラフ $G'$ であって，頂点 $1$ が頂点 $2, 3, \ldots, d_1+1$ に隣接するようなものが存在する．

【定理 4】の不等式の形から導出することもできますが，ここでは独立に【定理 6】の証明をすることにします．

$G$ において頂点 $1$ と隣接する頂点全体を $S$ とします． $S\neq \lbrace 2,3,\ldots,d_1+1\rbrace$ のときに，上手くグラフをとりなおすことで $S$ の総和を小さくできることを示せばよいです．

$S\neq \lbrace 2,3,\ldots,d_1+1\rbrace$ のとき，$i<j$ かつ $i\notin S, j\in S$ を満たす頂点 $i,j$ があります． $d_i=d_j$ ならば，頂点 $i$ と頂点 $j$ の番号を入れ替えればよいです．

$d_i > d_j$ ならば，頂点 $i$ と隣接し頂点 $j$ とは隣接していない頂点 $u$ があるので，$G$ から辺 $1j$, $iu$ を除き辺 $1i, ju$ を追加すればよいです． $\blacksquare$

アルゴリズム

【定理 6】から，$d$ がある単純無向グラフの次数列であるとき，次のアルゴリズムによって $d$ を次数列とする単純無向グラフをひとつ構成できることが分かります．このアルゴリズムを Havel–Hakimi アルゴリズムといいます．

辺集合 $E$ を空集合で初期化する．
次を繰り返す．
- 頂点 $i$ 全体を $d_i$ について降順に並べたとき，$i_1,i_2,\ldots,i_n$ であるとする．
- $k=d_{i_1}$ とする．$k=0$ ならば終了する．
- $j=2,3,\ldots,k+1$ について次を行う：辺 $i_1i_j$ を $E$ に追加し，$d_{i_j}$ から $1$ を引く．
- $d_{i_1}$ を $0$ にする．

なお $d$ が単純無向グラフの次数列でないときには，アルゴリズムの過程で $d_i$ が $n$ 以上の整数や負の整数になります．このような場合を検出することでこのアルゴリズムは非負整数列 $d$ が単純無向グラフの次数列であるか否かを判定するアルゴリズムとして用いることもできます．

6. 補足：計算量について

$d$ を $0$ 以上 $n-1$ 以下の整数からなる長さ $n$ の列とします．

$d$ を次数列とする単純無向グラフが存在するか否かは，【定理 4】を用いると $\mathrm{O}(n)$ 時間で判定できます．計数ソートや累積和などによる実装が可能です．

また，Havel–Hakimi アルゴリズムを用いると，$\mathrm{O}(n+\sum_i d_i)$ 時間で $d$ を次数列とする単純無向グラフが存在するかを判定し，存在するならばそれを構成することができます．ただし余分な $\log n$ などを回避するには，常に頂点順が $d_i$ に関してソートされた状態を保つなどの実装の工夫が必要となります．詳しくは次の実装例を参照してください．

6.1. 実装例

Codeforces Testing Round 3 "C. Swaps" での提出です．

https://codeforces.com/contest/134/submission/363239399

この実装例では，次数列のソートを行う際に時間計算量 $\mathrm{O}(n\log n)$ をかけていますが，この部分はバケットソートなどを用いることで $\mathrm{O}(n)$ 時間とすることが可能です．

7. 関連問題

1 は本記事の内容がほとんどそのまま問われている問題です．

2, 3 は $\text{Erd\H{o}s--Gallai}$ の定理を用いて非負整数列が単純無向グラフの次数列となるかを判定することに関する問題です．

8. まとめ

本記事では，非負整数列が単純無向グラフの次数列となる条件を記述した $\text{Erd\H{o}s--Gallai}$ の定理を証明しました．

さらに，非負整数列が単純無向グラフの次数列となる場合に実際にそのような単純無向グラフを構成する Havel–Hakimi アルゴリズムを解説しました．

これらはグラフ理論の基礎的な結果であると同時に，証明手法についてもパズルのように辺を繋ぎ変える巧妙な操作を行うという，グラフ理論特有の面白いものだと思います．楽しんでいただければ幸いです．

9. 参考文献

Wikipedia．Erdős–Gallai theorem．https://en.wikipedia.org/wiki/Erdős–Gallai_theorem．（閲覧日: 2026-03-31）．
P. Erdős, T. Gallai．Graphs with prescribed degree of vertices．Mat. Lapok.．Vol. 11．pp. 264–274．1960．https://cir.nii.ac.jp/crid/1573950400633072000．
Václav Havel．A remark on the existence of finite graphs．Časopis pro pěstování matematiky．Vol. 80．No. 4．pp. 477–480．1955．DOI: 10.21136/CPM.1955.108220．https://doi.org/10.21136/CPM.1955.108220．
S. L. Hakimi．On realizability of a set of integers as degrees of the vertices of a linear graph. I．Journal of the Society for Industrial and Applied Mathematics．Vol. 10．No. 3．pp. 496–506．1962．DOI: 10.1137/0110037．https://doi.org/10.1137/0110037．
S. A. Choudum．A simple proof of the Erdős–Gallai theorem on graph sequences．Bulletin of the Australian Mathematical Society．Vol. 33．No. 1．pp. 67–70．1986．DOI: 10.1017/S0004972700002872．https://doi.org/10.1017/S0004972700002872．
Amitabha Tripathi, Sushmita Venugopalan, Douglas B. West．A short constructive proof of the Erdős–Gallai characterization of graphic lists．Discrete Mathematics．Vol. 310．No. 4．pp. 843–844．2010．DOI: 10.1016/j.disc.2009.09.023．https://doi.org/10.1016/j.disc.2009.09.023．

トップページ：AtCoder Algorithm Lectures