Petersenの定理(完全マッチング)

同義語:Petersen's theorem (perfect matching)Petersenの1-因子定理Petersen's 1-factor theoremペテルセンの定理(完全マッチング)

概要

Petersenの定理(完全マッチング)(Petersen's theorem)とは、橋をもたない有限の 3-正則グラフは完全マッチング(1-因子)をもつという定理である。Tutte の 1-因子定理の条件を、奇成分から外へ出る辺の本数の数え上げで確かめて証明される。同じ数え上げと偶奇の議論により、どの 2 本の辺を除いても完全マッチングが残り、どの辺も完全マッチングに含まれる。橋があると成り立たないことがあり(単純グラフの最小の反例は 16 頂点)、完全マッチングが存在しても辺集合を完全マッチングに分けられるとは限らない(Petersen グラフ)。

$$\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}} $$

前提知識: マッチング(グラフ理論), Tutteの定理

Petersen の定理(Petersen's theorem)とは、橋をもたない有限の 3-正則グラフは完全マッチングをもつ、という定理である。すなわち、どの頂点の次数も $3$ で、1 本の辺を除いても連結成分の個数が増えないグラフでは、すべての頂点を辺でちょうど 1 回ずつ覆う辺の集合が見つかる。J. Petersen が 1891 年に示した結果で(Die25 Corollary 2.2.2、p. 45、BM76 Corollary 5.4、p. 79)、今では Tutteの定理 の短い系として証明される。
同じ Petersen の名をもつ定理に、すべての次数が偶数 $2k$ のループのない有限な多重グラフが 2-因子に分解されるという定理がある(多重グラフ の定理「Petersen の 2-因子定理」)。この記事で扱うのは、それとは別の、完全マッチング(1-因子)についての定理である。
この記事では、主定理を奇成分の数え上げで証明したあと、同じ数え上げで得られる強い形を示す。橋をもたない 3-正則グラフでは、どの 2 本の辺を除いても完全マッチングが残り、どの辺も完全マッチングに含まれる。さらに、次数 $r$ への一般化を述べ、橋があるときに定理が成り立たなくなること、単純グラフでのそのような反例の最小の頂点数が $16$ であること、Petersenグラフ が完全マッチングをもつのに辺集合を完全マッチングに分けられないことを確かめる。

定義

この記事のグラフ $G=(V,E)$ は、とくに断らない限り有限の単純無向グラフとする。連結性を仮定しない。

完全マッチング・橋・3-正則グラフ
  1. マッチングとは、どの 2 本も端点を共有しない辺の集合である。すべての頂点を端点にもつマッチングを完全マッチング、または 1-因子という。
  2. 辺 $e$ を除くと連結成分の個数が増えるとき、$e$ を橋(bridge)という。
  3. すべての頂点の次数が $r$ のグラフを $r$-正則グラフといい、$r=3$ のものを 3-正則グラフ(立方グラフ)という。

完全マッチング $M$ があれば、$\lvert V\rvert=2\lvert M\rvert$ なので頂点数は偶数である。3-正則グラフでは、次数の和 $3\lvert V\rvert$ が辺の本数の 2 倍なので、頂点数はいつも偶数である。
頂点の集合 $C\subset V$ について、端点の一方だけが $C$ に属する辺の集合を $\partial C$ と書く。

切れ目の本数の偶奇

$G$ を橋をもたない 3-正則グラフ、$C\subset V$ を頂点数が奇数の集合とすると、$\lvert\partial C\rvert\ge3$ である。

$C$ の頂点の次数の和を、$C$ の内部の辺の本数 $e_C$ を使って数えると $3\lvert C\rvert=2e_C+\lvert\partial C\rvert$ である。$\lvert C\rvert$ は奇数なので $\lvert\partial C\rvert$ は奇数であり、$1$ 以上である。
$\lvert\partial C\rvert=1$ とし、$\partial C=\{e\}$、$e=xy$($x\in C$、$y\notin C$)とする。$G$ から $e$ を除くと、$C$ の頂点と $C$ の外の頂点を結ぶ辺はなくなるので、$x$ と $y$ は別の連結成分に入る。$G$ では $x,y$ は同じ連結成分にあるから、$e$ は橋であり、仮定に反する。よって $\lvert\partial C\rvert\ge3$ である。$\square$

グラフ $H$ の連結成分のうち頂点数が奇数のものを奇成分といい、その個数を $o(H)$ と書く。$S\subset V$ について、$S$ の頂点とそれに接続する辺を除いたグラフを $H-S$ と書く。証明の土台は次の判定法である。

奇成分による判定

有限グラフ $H$ が完全マッチングをもつための必要十分条件は、$H$ のすべての頂点の部分集合 $S$ について $o(H-S)\le\lvert S\rvert$ が成り立つことである。

これは Tutte の 1-因子定理そのものであり(Die25 Theorem 2.2.1、p. 44)、証明は Tutteの定理 の記事にある。必要性の部分は、奇成分は頂点が奇数個なので少なくとも 1 頂点が成分の外の $S$ の頂点と組むしかない、という観察である。

主定理

Petersen の定理

橋をもたない有限の 3-正則グラフは完全マッチングをもつ。

奇成分の数え上げ

$G=(V,E)$ を橋をもたない 3-正則グラフとし、thm-pm-tutte の条件を確かめる。$S\subset V$ とし、$C_1,\dots,C_q$ を $G-S$ の奇成分とする。
lem-pm-parity により $\lvert\partial C_i\rvert\ge3$ である。$C_i$ は $G-S$ の連結成分なので、$\partial C_i$ の辺の $C_i$ の外の端点はすべて $S$ に属する。$C_i$ は互いに交わらないので、$\partial C_1,\dots,\partial C_q$ の辺はどれも $S$ の頂点に接続する相異なる辺である。$S$ の頂点に接続する辺は全部で $3\lvert S\rvert$ 本以下なので
$$ 3q\le\sum_{i=1}^q\lvert\partial C_i\rvert\le3\lvert S\rvert $$
であり、$o(G-S)=q\le\lvert S\rvert$ である。$\square$

$S$ の各頂点は外へ高々 3 本の辺しか出せないのに、各奇成分は 3 本以上の辺を受け取らなければならない。橋がないという仮定は、この「3 本以上」にだけ使われている。証明は Die25 p. 45、BM76 p. 79 と同じ筋である。

強い形:どの 2 本の辺を除いても残る

主定理の数え上げでは、各奇成分が 3 本以上の辺を外へ出すことを使った。そのうちの数本が $S$ に届かなくても、奇成分の個数は $\lvert S\rvert$ をわずかしか超えられない。さらに偶奇を使うと、その超過も消える。

2 本の辺を避ける完全マッチング

$G$ を橋をもたない有限の 3-正則グラフとし、$F\subset E$ を $\lvert F\rvert\le2$ の辺の集合とする。このとき $G$ は $F$ の辺を使わない完全マッチングをもつ。

$H$ を $G$ から $F$ の辺だけを除いたグラフ(頂点集合は $V$)とし、thm-pm-tutte の条件を $H$ について確かめる。$S\subset V$ とし、$C_1,\dots,C_q$ を $H-S$ の奇成分とする。
lem-pm-parity により、$G$ で $\lvert\partial C_i\rvert\ge3$ である。$\partial C_i$ の辺は、$F$ に属するか、そうでなければ $H$ の辺で、$C_i$ が $H-S$ の連結成分なので $S$ の頂点に接続する。$F$ の各辺は 2 つの $C_i$ の境界に高々 1 回ずつ現れ、$S$ の頂点に接続する辺は $3\lvert S\rvert$ 本以下なので
$$ 3q\le\sum_{i=1}^q\lvert\partial C_i\rvert\le3\lvert S\rvert+2\lvert F\rvert\le3\lvert S\rvert+4 $$
である。よって $q\le\lvert S\rvert+\frac43$、すなわち $q\le\lvert S\rvert+1$ である。
一方、$V\setminus S$ は $H-S$ の連結成分の交わらない和で、偶成分の頂点数は偶数なので、$q\equiv\lvert V\rvert-\lvert S\rvert\pmod2$ である。$\lvert V\rvert$ は偶数なので $q\equiv\lvert S\rvert\pmod2$ である。したがって $q=\lvert S\rvert+1$ は起こらず、$q\le\lvert S\rvert$ である。thm-pm-tutte により $H$ は完全マッチングをもち、それは $F$ の辺を使わない $G$ の完全マッチングである。$\square$

辺と完全マッチング

$G$ を橋をもたない有限の 3-正則グラフとする。
(1) $G$ のどの辺 $e$ についても、$e$ を含む完全マッチングと、$e$ を含まない完全マッチングがある。
(2) $G$ が頂点をもつなら、$G$ の相異なる完全マッチングは $3$ 個以上ある。
(3) 完全マッチング $M$ を除いた $(V,E\setminus M)$ の連結成分は閉路であり、$G$ の辺集合は 1-因子と 2-因子に分かれる。

  1. $e$ を含まないものは、$F=\{e\}$ として thm-pm-avoid から得られる。$e=xy$ を含むものを作る。$x$ に接続する $e$ 以外の 2 本の辺を $F$ とすると、$F$ を使わない完全マッチングは $x$ を覆うために $e$ を使うしかない。
  2. 頂点 $x$ に接続する 3 本の辺のそれぞれについて、それを含む完全マッチングが (1) によりある。1 つのマッチングは $x$ に接続する辺を 1 本しか含まないので、この 3 つは相異なる。
  3. $(V,E\setminus M)$ のどの頂点の次数も $3-1=2$ なので、連結成分は閉路である。$\square$

たとえば $K_4$ の頂点 $x,y,z,t$ で $F=\{xz,xt\}$ とすると、$F$ を使わない完全マッチングは $\{xy,zt\}$ だけである。
除く辺が $3$ 本になると結論は成り立たない(1 頂点に接続する 3 本の辺を除けばその頂点が孤立する)ので、「2 本」は最良である。(2) の $3$ も最良で、完全グラフ $K_4$ の完全マッチングはちょうど $3$ 個である。
同じ数え上げは次数 $r$ でも働く。

次数 $r$ への一般化

$r\ge2$ とし、$G$ を頂点数が偶数の連結な $r$-正則グラフとする。$r-2$ 本以下のどの辺を除いても $G$ が連結のままなら、$G$ は完全マッチングをもつ。

$\lvert C\rvert$ を奇数とすると、$C\neq V$ であり($\lvert V\rvert$ は偶数)、$C$ は空でない。$\partial C$ の辺をすべて除くと $C$ とその外が切り離されるので、仮定から $\lvert\partial C\rvert\ge r-1$ である。$r\lvert C\rvert=2e_C+\lvert\partial C\rvert$ から $\lvert\partial C\rvert\equiv r\lvert C\rvert\equiv r\pmod2$ なので、$\lvert\partial C\rvert\ge r$ である。あとは prf-pm-main と同じく、$G-S$ の奇成分の個数を $q$ として $rq\le r\lvert S\rvert$ から $q\le\lvert S\rvert$ を得る。$\square$

$r=3$ の連結グラフでは、「$1$ 本の辺を除いても連結」は橋がないことであり、頂点数は自動的に偶数である。

例

次の表のグラフは、どれも橋をもたない 3-正則グラフである。完全マッチングの個数は、書き出して数える有限の計算である。

グラフ頂点数完全マッチングの個数辺を 3 つの完全マッチングに分けられるか
$K_4$$4$$3$分けられる
三角柱$6$$4$分けられる
完全二部グラフ $K_{3,3}$$6$$6$分けられる
Petersenグラフ$10$$6$分けられない
Hamilton 閉路をもつ場合

3-正則グラフ $G$ が Hamilton閉路 $v_0v_1\dots v_{n-1}v_0$ をもつとする。$n$ は偶数なので、閉路の辺を 1 本おきに選ぶと 2 つの完全マッチングが得られ、閉路に属さない辺の集合が 3 つ目の完全マッチングになる。したがって、この場合は Tutte の定理を使わずに完全マッチングが見つかり、辺集合は 3 つの完全マッチングに分かれる。このとき $G$ に橋はない。閉路の辺は閉路に含まれるので橋でなく、閉路に属さない辺も、除いたあと両端が閉路でつながっているので橋でない。

五角形と五芒星の図で見る完全マッチング

Petersenグラフ $P$ を、外側の五角形 $u_0u_1u_2u_3u_4$、内側の五芒星 $w_0w_2w_4w_1w_3$、スポーク $u_iw_i$ で描く。どの辺も長さ $5$ の閉路に含まれるので橋はなく、thm-pm-main が当てはまる。実際、スポーク 5 本は完全マッチングである。
$P$ の完全マッチングはちょうど $6$ 個で、どの辺もちょうど $2$ 個に含まれ、相異なる 2 つの完全マッチングはちょうど 1 本の辺を共有する(有限の計算)。どの完全マッチングでも、補集合は長さ $5$ の閉路 2 本である(Petersenグラフ の補題「完全マッチングの補集合」)。
一方、$P$ の辺集合を 3 つの完全マッチングに分けることはできない(Petersenグラフ の定理「Petersen グラフの辺彩色数」)。thm-pm-main と cor-pm-edge は完全マッチングの存在を保証するだけで、辺全体の分解までは保証しない。この点で、$r$-正則二部グラフの辺集合がいつも $r$ 個の完全マッチングに分かれること(多重グラフ の定理「König の辺彩色定理」)とは異なる。

橋があるとき

橋があると、定理の結論は成り立つことも成り立たないこともある。

反例:完全マッチングをもたない 16 頂点のグラフ

完全グラフ $K_4$ の頂点を $a,b,x,y$ とし、辺 $ab$ を除いて、新しい頂点 $w$ と辺 $wa,wb$ を加えたグラフを $B$ とする。$B$ は $5$ 頂点で、$w$ の次数だけが $2$ である。$B$ を 3 つ用意し、新しい頂点 $c$ を 3 つの $w$ と結ぶと、16 頂点の 3-正則グラフ $G$ が得られる。
$G-\{c\}$ は $B$ の 3 つの写しであり、どれも奇成分なので、$o(G-\{c\})=3>1$ である。よって thm-pm-tutte により $G$ は完全マッチングをもたない(正則グラフ の例「反例:完全マッチングをもたない立方グラフ」)。$c$ から出る 3 本の辺はどれも橋である。
この例は、3-正則であること $\not\Rightarrow$ 完全マッチングをもつこと、を示す。満たされていない仮定は「橋をもたない」である。

反例の最小の頂点数

完全マッチングをもたない有限の単純な 3-正則グラフの頂点数は $16$ 以上である。

要点:thm-pm-tutte の障害となる $S$ をとると、辺を 1 本しか受け取らない奇成分が 3 個以上あり、そのそれぞれが 5 頂点以上をもつ。

詳しい証明を開く

$G$ を完全マッチングをもたない 3-正則グラフとする。thm-pm-tutte により $o(G-S)>\lvert S\rvert$ となる $S$ がある。$\lvert V\rvert$ は偶数なので prf-pm-avoid と同じく $o(G-S)\equiv\lvert S\rvert\pmod2$ であり、$q:=o(G-S)\ge\lvert S\rvert+2$ である。奇成分 $C$ について $\lvert\partial C\rvert$ は奇数である(prf-pm-parity の前半)。$\lvert\partial C\rvert=1$ となる奇成分の個数を $a$ とすると、ほかの奇成分は $\lvert\partial C\rvert\ge3$ なので、$a+3(q-a)\le3\lvert S\rvert$、すなわち $2a\ge3(q-\lvert S\rvert)\ge6$ で、$a\ge3$ である。

$\lvert\partial C\rvert=1$ の奇成分 $C$ の頂点数を調べる。$3\lvert C\rvert=2e_C+1$ である。$\lvert C\rvert=1$ なら $e_C=1$ で、$1$ 頂点に辺があることになり不可能である。$\lvert C\rvert=3$ なら $e_C=4$ で、$3$ 頂点の単純グラフの辺は $3$ 本以下なので不可能である。よって $\lvert C\rvert\ge5$ である。

また $a\ge1$ なので $\partial C$ の辺の端点が $S$ にあり、$\lvert S\rvert\ge1$ である。以上から $\lvert V\rvert\ge\lvert S\rvert+5a\ge1+15=16$ である。$\square$

ex-pm-sixteen により、この下界は達成される。一方、橋があっても完全マッチングをもつグラフもある。

橋があるが完全マッチングをもつ 10 頂点のグラフ

ex-pm-sixteen の $B$ を 2 つ用意し、2 つの $w$ を辺で結ぶと、10 頂点の 3-正則グラフができる。結んだ辺は橋である。この橋と、各 $B$ の中の辺 $ax$、$by$ を合わせると、完全マッチングになる。よって「橋をもたない」は完全マッチングの存在の十分条件であって、必要条件ではない。ただしこのグラフでは、どの完全マッチングも橋を含む。橋を含まないとすると、各 $B$ の奇数個の頂点が内部の辺だけで覆われることになるからである。したがって cor-pm-edge の (1) は成り立たない。

次の表の各行は、条件を 1 つだけ替えたときに成り立たなくなることを示す。

替える条件反例成り立たなくなること
thm-pm-main の「橋をもたない」ex-pm-sixteen の 16 頂点のグラフ完全マッチングの存在
thm-pm-main の「3-正則」(次数をそろえない)$K_{2,4}$(橋をもたない。次数は $4$ と $2$)完全マッチングの存在
thm-pm-main の次数 $3$(次数 $2$ にする)長さ $5$ の閉路 2 つの非交和完全マッチングの存在
thm-pm-avoid の $\lvert F\rvert\le2$($3$ 本にする)1 頂点に接続する 3 本の辺$F$ を使わない完全マッチングの存在
prop-pm-regular の頂点数が偶数完全グラフ $K_5$($r=4$)完全マッチングの存在

$K_{2,4}$ の部集合を $\{x_1,x_2\}$、$\{y_1,\dots,y_4\}$ とする。どの辺も長さ $4$ の閉路に含まれるので橋はなく、$S=\{x_1,x_2\}$ で $o(K_{2,4}-S)=4>2$ である。長さ $5$ の閉路 2 つの非交和は頂点数が $10$ で橋がなく、各成分の頂点数が奇数なので完全マッチングはない。$K_5$ はどの $2$ 本の辺を除いても連結だが、頂点数が奇数である。

補足

  • 多重グラフ:橋をもたない 3-正則の多重グラフ(ループを許す)にも定理は成り立つ。ループのある頂点から出るもう 1 本の辺は橋になるので、ループはない。lem-pm-parity と prf-pm-main は平行辺があっても同じに働き、thm-pm-tutte の条件は平行辺を 1 本にまとめたグラフの条件と同じである。一方、prop-pm-minimal は単純グラフに限る主張である。ex-pm-sixteen の $B$ の代わりに、3 頂点 $x,y,z$ と二重の辺 $xy$、辺 $xz$、$yz$ からなる多重グラフ($z$ の次数だけが $2$)を使うと、完全マッチングをもたない 10 頂点の 3-正則の多重グラフが得られる。
  • 3-辺彩色:3-正則グラフの辺集合を 3 つの完全マッチングに分けることは、辺を 3 色で塗る 辺彩色 にほかならない。cor-pm-edge の (3) の 2-因子のすべての閉路の長さが偶数なら、閉路を 2 色で交互に塗り、$M$ を第 3 の色で塗ればよい。Petersenグラフ はこれができない例である。
  • 計算:最大マッチングは Edmondsの花アルゴリズム で多項式時間で求まる。
  • 歴史:Petersen の結果は 1891 年で、Tutteの定理(1947 年)より半世紀以上前のものである。Tutte の定理を使うと、上のように数行の数え上げで示せる。

関連項目

参考文献

[1]
Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer, 2025, §2.2:Theorem 2.2.1(p. 44)、Corollary 2.2.2 とその証明(p. 45)

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