Erdős–Pósaの定理

同義語:Erdős-Pósaの定理Erdős–Pósa theoremErdős–Pósaの性質Erdős–Pósa property

概要

Erdős–Pósaの定理(Erdős–Pósa theorem)とは、関数 $f(k)$ があって、どんな有限グラフも互いに頂点を共有しない $k$ 個の閉路をもつか、$f(k)$ 個以下の頂点からなる集合ですべての閉路と交わるものをもつ、という定理である。$f(k)$ は $k\log k$ の定数倍にとれ、この増え方は定数倍を除いて最良である。最小次数 3 のグラフの短い閉路と、次数 3 の多重グラフでの帰納法で証明され、下界は確率論的な構成による。マイナーの理論で平面グラフの場合へ一般化される。

$$\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–Pósa の定理(Erdős–Pósa theorem)は、グラフの閉路について「互いに頂点を共有しない閉路をたくさん詰め込めない」ことと「少数の頂点ですべての閉路を断てる」ことがほぼ同じであることを述べる定理である。正確には、関数 $f(k)$ があって、どんな有限グラフも、互いに頂点を共有しない $k$ 個の閉路をもつか、$f(k)$ 個以下の頂点からなる集合ですべての閉路と交わるものをもつ。しかも $f(k)$ は $k\log k$ の定数倍にとれ、この増え方は定数倍を除いて最良である。
$k$ 個の頂点素な閉路があれば、すべての閉路を断つには $k$ 個以上の頂点が要る。定理はその逆向きを、$k$ の関数の分だけの損失で保証する。二部グラフで「最大マッチングの大きさ=最小頂点被覆の大きさ」が成り立つ Kőnig の定理(マッチング(グラフ理論))と違い、閉路では等号は成り立たない(ex-ep-small)が、比が $\log k$ 程度に収まる。この「詰め込み」と「被覆」を関数で結ぶ性質は、定理にちなんで Erdős–Pósa の性質 とよばれ、グラフマイナーの理論で大きく一般化された。
この記事では、Simonovits による証明を Die25 に沿って一行ずつ述べ、$f(k)=O(k\log k)$ を示す。次に、$k\log k$ が最良であることを示した Erdős–Pósa の確率論的な構成の筋を述べ、その決定的な部分を証明する。

定義

この記事のグラフは有限の単純グラフとし、証明の途中でだけ、ループと多重辺を許す 多重グラフ を使う。多重グラフでは、1 本のループは長さ 1 の閉路、2 頂点を結ぶ 2 本の辺は長さ 2 の閉路とみなし、ループは次数を 2 増やす。対数 $\log$ の底は $2$ とする。

閉路の詰め込みと被覆

グラフ $G$ について、互いに頂点を共有しない閉路の最大個数を $\nu(G)$ と書く。頂点の集合 $X$ で、$G$ のすべての閉路が $X$ の頂点を通るものを、閉路を断つ集合(feedback vertex set)といい、その最小の大きさを $\tau(G)$ と書く。

$\nu(G)$ 個の頂点素な閉路は、閉路を断つ集合の異なる頂点を 1 つずつ含むので、$\nu(G)\le\tau(G)$ である。閉路を断つ集合を除いた残りは閉路のないグラフ、すなわち 森(グラフ理論) である。

Erdős–Pósa の性質

グラフの族 $\mathcal H$ が Erdős–Pósa の性質 をもつとは、関数 $f\colon\mathbb N\to\mathbb N$ があって、任意の $k$ と任意のグラフ $G$ について、$G$ が $\mathcal H$ のグラフと同型な互いに頂点素な部分グラフを $k$ 個もつか、$f(k)$ 個以下の頂点の集合 $X$ で $G-X$ が $\mathcal H$ のグラフと同型な部分グラフをもたないものがあることをいう。

小さいグラフの $\nu$ と $\tau$
  1. 完全グラフ $K_5$:2 つの頂点素な閉路には 6 頂点以上が要るので $\nu=1$ である。2 頂点を除いても三角形 $K_3$ が残り、3 頂点を除くと辺 1 本だけが残るので $\tau=3$ である。
  2. 完全二部グラフ $K_{3,3}$:閉路の長さは 4 以上なので頂点素な 2 つの閉路には 8 頂点が要り、$\nu=1$ である。1 頂点を除くと $K_{2,3}$ が残り閉路をもつ。同じ側の 2 頂点を除くと $K_{1,3}$ という木が残るので $\tau=2$ である。
  3. Petersenグラフ:外側と内側の 5 角形が頂点素なので $\nu\ge2$、10 頂点で内周 5 なので $\nu=2$ である。$\tau=3$ であることは計算機で全数を調べて確かめた。
    1 から、頂点素な 2 つの閉路をもたない($\nu(G)\le1$)グラフでも $\tau(G)=3$ となりうるので、thm-ep-main の形の主張では $f(2)\ge3$ でなければならない。Kőnig の定理のような等式 $\tau=\nu$ は閉路では成り立たない。

主定理

$k\in\mathbb N$ について
$$r_k:=\log k+\log\log k+4,\qquad s_k:=\begin{cases}4kr_k&(k\ge2)\\1&(k\le1)\end{cases}$$
とおく。$s_2=40$ で、$s_k$ はほぼ $4k\log k$ である。

Erdős–Pósa の定理

$f(k):=\lfloor s_k+k-1\rfloor$ とする。任意の $k\in\mathbb N$ と任意のグラフ $G$ について、$G$ は互いに頂点素な $k$ 個の閉路をもつか、$f(k)$ 個以下の頂点からなる閉路を断つ集合をもつ。とくに $f(k)=O(k\log k)$ であり、閉路の族は Erdős–Pósa の性質をもつ。

所在

定理は Die25 Theorem 2.3.2(p. 49)で、同書は Erdős と Pósa(1965)に帰し、証明は本質的に Simonovits によるとしている(第 2 章の注、p. 60)。EP65 の定理(p. 347)は、$\nu(G)=k$ のグラフ全体での $\tau(G)$ の最大値 $r(k)$ について、絶対定数 $c_1,c_2>0$ で $c_1k\log k< r(k)< c_2k\log k$($k\ge2$)となることを述べている。$f(1),f(2),\dots,f(5)$ の値は $1,41,76,115,154$ で、定数は良くないが、増え方は最良である(thm-ep-lower)。

証明は 3 段からなる。まず最小次数 3 のグラフには短い閉路があることを示す(lem-ep-girth)。次に、すべての頂点の次数が 3 の多重グラフは、頂点が $s_k$ 個以上あれば $k$ 個の頂点素な閉路をもつことを、最短の閉路を取り除く帰納法で示す(lem-ep-cubic)。最後に、一般のグラフから次数が 2 か 3 の極大な部分グラフを取り出し、その次数 3 の頂点に補題を使う。

短い閉路

閉路の長さの最小値を 内周(girth)といい $g(G)$ と書く(閉路)。

最小次数 3 のグラフの内周

単純グラフ $G$ のすべての頂点の次数が 3 以上なら、$g(G)\le2\log|G|$ である($|G|$ は頂点の個数)。

幅優先に広がる木を数える

$G$ は閉路をもつ(極大な道の端点の隣接頂点を考えればよい)ので $g:=g(G)$ は有限で、$g\ge3$ である。$\rho:=\lfloor(g-1)/2\rfloor$ とおき、頂点 $v$ を 1 つ固定して、$v$ からの距離がちょうど $i$ の頂点の個数を $N_i$ とする。$1\le i<\rho$ のとき $N_{i+1}\ge2N_i$ を示す。距離 $i$ の頂点 $u$ について、(a) 距離 $i-1$ の隣接頂点は 1 つだけである(2 つあれば、$v$ からの 2 本の最短の道の和に長さ $2i$ 以下の閉路ができ、$2i< g$ に反する)。(b) 距離 $i$ の頂点とは隣接しない(隣接すれば長さ $2i+1$ 以下の閉路ができ、$2i+1\le2\rho-1< g$ に反する)。よって $u$ の残りの 2 つ以上の隣接頂点は距離 $i+1$ にある。(c) 距離 $i$ の異なる 2 頂点が距離 $i+1$ の同じ頂点に隣接することはない(長さ $2i+2$ 以下の閉路ができ、$2i+2\le2\rho< g$ に反する)。よって $N_{i+1}\ge2N_i$ である。$N_1\ge3$ なので $N_i\ge3\cdot2^{i-1}$($1\le i\le\rho$)であり、
$$|G|\ge1+\sum_{i=1}^{\rho}3\cdot2^{i-1}=3\cdot2^{\rho}-2$$
となる。$\rho\ge(g-2)/2$ なので $2^{(g-2)/2}\le2^\rho\le(|G|+2)/3$、すなわち $g\le2\log\bigl(2(|G|+2)/3\bigr)$ である。次数 3 の頂点とその隣接頂点で $|G|\ge4$ なので $2(|G|+2)/3\le|G|$ であり、$g\le2\log|G|$ が従う。$\square$

これは Die25 Corollary 1.3.5(p. 10、不等号は狭義)にあたる。ループや多重辺をもつ多重グラフでは $g\le2$ である。

3 正則な多重グラフ

すべての頂点の次数が 3 の多重グラフを 3 正則多重グラフ という(単純グラフの場合は 立方グラフ)。多重グラフ $H$ のすべての頂点の次数が 2 か 3 で、どの連結成分も次数 3 の頂点を含むとき、次数 2 の頂点だけを内部にもつ極大な道(両端は次数 3 の頂点で、一致してもよい)をそれぞれ 1 本の辺(両端が一致すればループ)に置き換えると、次数 3 の頂点だけを頂点とする 3 正則多重グラフ $\hat H$ が得られる。これを次数 2 の頂点の 平滑化 という。$\hat H$ の閉路の各辺をもとの道に戻すと $H$ の閉路になり、$\hat H$ の頂点素な閉路は $H$ の頂点素な閉路に戻る(次数 2 の頂点はちょうど 1 本の道の内部にあるので)。

3 正則多重グラフの頂点素な閉路

$k\in\mathbb N$ とし、$H$ を 3 正則多重グラフとする。$|H|\ge s_k$ なら、$H$ は互いに頂点素な $k$ 個の閉路をもつ。

最短の閉路を取り除く帰納法

$k$ に関する帰納法による。$k=0$ は自明で、$k=1$ では $H$ は空でなく、すべての次数が 2 以上なので閉路をもつ。$k\ge2$ とし、$k-1$ で主張が成り立つとする。$H$ の最短の閉路を $C$ とする。
(1) $H-C$ は大きな 3 正則多重グラフの細分を含む。 $C$ の頂点と $C$ の外の頂点を結ぶ辺の本数を $m$ とする。$C$ の頂点の次数の和は $3|C|$ で、そのうち $2|C|$ は $C$ の辺の分なので、残りは $|C|$ である。外へ出る辺はそれを 1、$C$ の頂点どうしを結ぶ $C$ 以外の辺は 2 使うので、$m\le|C|$ である。
頂点の分割 $V(H)=V_1\sqcup V_2$ を、$V_1:=V(C)$ から始めて次のように動かす:$V_2$ が誘導する部分 $H[V_2]$ で次数が 1 以下の頂点があれば、それを $V_1$ へ移す。その頂点は $H$ で次数 3 で、ループをもてば $H[V_2]$ での次数が 2 以上になるのでループはなく、$V_2$ の中への辺は 1 本以下、$V_1$ への辺は 2 本以上である。よって 1 回移すごとに $V_1$ と $V_2$ を結ぶ辺は 1 本以上減る。これをちょうど $n$ 回行って止まったとすると、$V_1$ と $V_2$ を結ぶ辺は $m-n$ 本以下である。
止まった時点で $H[V_2]$ の頂点の次数は 2 か 3 である。次数 2 の頂点は $V_1$ への辺をちょうど 1 本もつので、その個数は $m-n$ 以下である。$H[V_2]$ から、すべての頂点の次数が 2 の連結成分(閉路)を除いて次数 2 の頂点を平滑化した 3 正則多重グラフを $H'$ とすると、$|V_2|=|H|-|C|-n$ なので
$$|H'|\ge|H|-|C|-n-(m-n)=|H|-|C|-m\ge|H|-2|C|.$$
(2) $|H'|\ge s_{k-1}$ である。 $|H|\ge s_k\ge s_2=40$ である。$|C|=g(H)\le2$ なら $|C|\le2\log|H|$ は明らかで、そうでなければ $H$ は単純な 3 正則グラフなので lem-ep-girth による。関数 $x\mapsto x-4\log x$ は導関数が $1-4/(x\ln2)$ なので $x\ge6$ で増加し、
$$|H'|\ge|H|-4\log|H|\ge s_k-4\log s_k$$
である。$s_k-4\log s_k\ge s_{k-1}$ を示せばよい。$k=2$ では $40-4\log40>18>1=s_1$ である。$k\ge3$ とする。$\log s_k=2+\log k+\log r_k$ なので
$$s_k-4\log s_k=4(k-1)r_k+4r_k-8-4\log k-4\log r_k=4(k-1)r_k+4\log\log k+8-4\log r_k$$
である。$r_k\ge r_{k-1}$ から $4(k-1)r_k\ge s_{k-1}$ なので、$\log r_k\le\log\log k+2$、すなわち $r_k\le4\log k$ を示せばよい。これは $\log\log k+4\le3\log k$ と同じで、$k=3$ では $r_3\approx6.25$、$4\log3\approx6.34$ により、$k\ge4$ では $\log k\ge2$ と $\log\log k\le\log k-1$ により $\log\log k+4\le\log k+3\le3\log k-1$ から成り立つ。
(3) 帰納法の仮定から $H'$ は頂点素な $k-1$ 個の閉路をもち、それらは平滑化を戻すと $H[V_2]\subseteq H-C$ の頂点素な閉路になる。$C$ を加えて $k$ 個の頂点素な閉路が得られる。$\square$

$\log\log k\le\log k-1$($k\ge4$)は、$y=\log k\ge2$ について $\log y\le y-1$ であることによる($y=2$ で等号、$y\ge2$ で右辺の増え方が大きい)。上の不等式は $2\le k\le200000$ の全部の $k$ で数値でも確かめた。この補題は Die25 Lemma 2.3.1(pp. 48–49)である。

主定理の証明

次数 2 か 3 の極大な部分グラフ

$k\ge1$ とし($k=0$ は自明)、$G$ をグラフとする。$G$ が閉路をもたなければ空集合が閉路を断つので、閉路をもつとする。閉路自身はすべての頂点の次数が 2 の部分グラフなので、$G$ の部分グラフで、すべての頂点の次数が 2 か 3 であるもののうち極大なもの $H$ がある。$H$ の次数 3 の頂点の集合を $U$ とする。以下、$H$ の極大性を何度も使う。両端が $H$ の次数 2 の相異なる頂点で、内部の頂点と辺が $H$ に属さない道(長さ 1 の辺でもよい)を $P$ とすると、$H\cup P$ は両端の次数が 3、内部の次数が 2 で、極大性に反する。よって そのような道はない。同様に、$H$ と交わらない閉路もない。
$\mathcal C$ を、$U$ と交わらず、$H$ とちょうど 1 頂点で交わる $G$ の閉路の全体とし、その頂点の集合を $Z\subseteq V(H)\setminus U$ とする。各 $z\in Z$ について、$H$ と $z$ だけで交わる $C_z\in\mathcal C$ を 1 つ選ぶ。$z\ne z'$ のとき $C_z$ と $C_{z'}$ は交わらない。交わるなら、$z$ から $C_z$ に沿って $C_{z'}$ に初めて着くまで進み、そこから $C_{z'}$ に沿って $z'$ へ行く道は、内部が $H$ の外にあり、両端が次数 2 の相異なる頂点で、上の そのような道 になるからである($C_z$ は $z'$ を通らないので、この道は辺 $zz'$ 1 本ではない)。
$\mathcal D$ を、$H$ の連結成分のうちすべての頂点の次数が 2 であり(閉路であり)$Z$ と交わらないものの全体とする。$\{C_z\}_{z\in Z}$ と $\mathcal D$ を合わせたものは頂点素な閉路の族である($C_z$ は $H$ と $z$ だけで交わる)。その個数が $k$ 以上なら定理が成り立つ。そうでなければ、$Z$ に $\mathcal D$ の各閉路から 1 頂点ずつ加えた集合 $X$ は $|X|\le k-1$ で、$\mathcal C$ のすべての閉路と $H$ のすべての閉路の成分に交わる。
$X\cup U$ は閉路を断つ。 $X$ と交わらない閉路 $D$ が $U$ とも交わらないとして矛盾を導く。$D$ は $H$ と交わる。$D\subseteq H$ なら、$D$ の頂点は $H$ で次数 2 なので $D$ は $H$ の連結成分であり、$X$ と交わるはずである。よって $D$ は $H$ に属さない辺 $e$ をもつ。$D$ が $H$ と 1 頂点だけで交わるなら $D\in\mathcal C$ で、$X$ と交わるはずである。$D$ が $H$ と 2 頂点以上で交わるなら、$D$ を $e$ から両方向にたどって初めて $H$ に着く頂点 $a,b$ は相異なり(同じなら $D$ と $H$ の共有点は 1 つ)、$D$ の $a$ から $b$ までの $e$ を含む部分は、両端が次数 2 の頂点($U$ の外)で内部と辺が $H$ の外にある道になり、矛盾する。
頂点の個数。 $H$ から $\mathcal D$ と、$Z$ と交わる閉路の成分を除いて次数 2 の頂点を平滑化すると、頂点の集合が $U$ の 3 正則多重グラフが得られる。$|U|\ge s_k$ なら lem-ep-cubic により $k$ 個の頂点素な閉路があり、平滑化を戻すと $G$ の頂点素な閉路になる。そうでなければ $|U|< s_k$ で、$|U|$ は整数なので $|U|\le\lfloor s_k\rfloor$($s_k$ が整数なら $s_k-1$ 以下)であり、$|X\cup U|\le k-1+\lfloor s_k\rfloor=f(k)$ である。$\square$

$k\log k$ が最良であること

下界

正の定数 $c$ があって、閉路の族に Erdős–Pósa の性質を与えるどんな関数 $f$ も、無限に多くの $k$ について $f(k)\ge ck\log k$ を満たす。

所在と証明の構成

EP65 はさらに、すべての $k$ について $r(k)>c_1k\log k$ となることを述べている(定理、p. 347)。証明は確率論的な構成で、作られるグラフを具体的に書き下すことはしていない(同所)。

その構成は次の 2 つの部分に分かれる。

  1. 確率論的な部分(EP65 Lemma 1・Lemma 2、pp. 348–350):$n$ が十分大きければ、$n$ 頂点で辺が $100n$ 本のグラフ $G$ で、次の (a)(b) を満たすものがある。(a) どの $\lfloor n/2\rfloor$ 個の頂点も、$G$ で $2n$ 本以上の辺を誘導する。(b) 長さ $L_n:=\lfloor(\ln n)/100\rfloor$ 以下の閉路は $n$ 個未満である($\ln$ は自然対数。EP65 は対数の底を書いていないが、底を $2$ と読んでも長さの上限が大きくなるだけなので、この形が従う)。
  2. 決定的な部分:(a)(b) から次の命題が従う。
    この記事では 1 を EP65 からの引用として使い(証明しない)、2 と、そこから thm-ep-lower を導く部分を証明する。
短い閉路を壊す

$n\ge2$、$L\ge1$ とし、$G$ を $n$ 頂点で辺が $100n$ 本以下のグラフで、上の (a) と、(b) で $L_n$ を $L$ に替えた条件を満たすものとする。$G$ の長さ $L$ 以下の各閉路から辺を 1 本ずつ除いたグラフを $G'$ とすると、$\nu(G')\le100n/L$ かつ $\tau(G')\ge n/2$ である。

辺を数える

除いた辺は $n$ 本未満である。$G'$ の閉路は長さ $L+1$ 以上で、頂点素な閉路は辺も共有しないので、$\nu(G')(L+1)\le100n$ である。
$X$ を $G'$ の閉路を断つ集合とし、$|X|< n/2$ と仮定する。$X$ の外の $n-|X|>n/2$ 個の頂点から $\lfloor n/2\rfloor$ 個を選ぶと、(a) によりそれらは $G$ で $2n$ 本以上の辺を誘導し、除いた辺は $n$ 本未満なので、$G'$ では $n$ 本より多く残る。一方 $G'-X$ は森なので、その $\lfloor n/2\rfloor$ 頂点の誘導部分グラフも森で、辺は $\lfloor n/2\rfloor-1$ 本以下で、$n$ 本より少ない。これは矛盾なので $\tau(G')\ge n/2$ である。$\square$

下界の導出

$f$ を閉路の族に Erdős–Pósa の性質を与える関数とする。十分大きい $n$ について、1 のグラフ $G$ に prop-ep-reduction を $L=L_n$ で使い、$G'$ と $K:=\nu(G')+1$ をとる。$G'$ は頂点素な $K$ 個の閉路をもたないので、$f$ の性質から $\tau(G')\le f(K)$ であり、$f(K)\ge n/2$ である。$n$ が大きければ $L_n\ge(\ln n)/200\ge(\log n)/300$($\ln n=(\ln2)\log n$ と $\ln2>2/3$ による)なので $K\le3\cdot10^4n/\log n+1\le n$ であり、
$$K\log K\le K\log n\le3\cdot10^4n+\log n\le4\cdot10^4n$$
となる。よって $f(K)\ge n/2\ge K\log K/(8\cdot10^4)$ である。$n\to\infty$ で $f(K)\ge n/2\to\infty$ なので、$K$ は無限に多くの値をとる。$c:=1/(8\cdot10^4)$ とすればよい。$\square$

定数はまったく最適化していない。上界の thm-ep-main の $f(k)\approx4k\log k$ と合わせて、$f$ の最良の増え方は $k\log k$ の定数倍である。

一般化

閉路をもつことは、三角形 $K_3$ をグラフマイナー としてもつことと同じである。Robertson と Seymour は、連結な平面グラフ $H$ について、$H$ をマイナーとしてもつグラフの族が Erdős–Pósa の性質をもつことを示した(Die25 Theorem 12.6.5、p. 393。証明は 木幅 の定理「禁止マイナーと格子」の 3(格子定理)による)。同書は、これが thm-ep-main を $H=K_3$ の場合として含み、$H$ が平面グラフでなければ成り立たない(演習 62)ことを述べている(p. 394)。また、閉路を辺素に詰め込み、辺で断つ版も同じ形で成り立つ(Die25 p. 49 は、上の証明を変えたものが第 7 章の演習 22 で示されると述べている)。この記事ではこれらを証明しない。

反例の表

強める・変える点例成り立たなくなること
損失なしの等式を求める$K_5$$\tau=\nu$($\nu=1$、$\tau=3$)
$f$ を $k$ の定数倍にするEP65 の確率論的構成$f(k)\le Ck$(thm-ep-lower)
閉路を、平面的でない $H$ のマイナーに替える$H=K_5$ などErdős–Pósa の性質(主張と所在のみ)
反例の確認

1 行目は ex-ep-small の 1 である。$K_5$ は閉路をもつので、等式は「詰め込み」の側を強めた形で成り立たない。2 行目:どんな定数 $C$ についても、$f(k)\le Ck$ がすべての $k$ で成り立てば、thm-ep-lower の $k$ のうち $\log k>C/c$ となるもので矛盾する。3 行目は Die25 演習 62(主張は p. 394)で、この記事では証明しない。

関連項目

参考文献

[1]
P. Erdős, L. Pósa, On independent circuits contained in a graph, Canadian Journal of Mathematics, 1965, pp. 347–352。定理(p. 347)、下界の確率論的証明と Lemma 1・Lemma 2(pp. 347–350)
[2]
Reinhard Diestel, Graph Theory, 6th edition, Graduate Texts in Mathematics 173, Springer, 2025, Corollary 1.3.5(p. 10)、§2.3(Lemma 2.3.1・Theorem 2.3.2、pp. 47–49)、第 2 章の注(p. 60)、Theorem 12.6.5 とその後の注意(pp. 393–394)

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