Chvátal–Erdősの定理(Chvátal–Erdős theorem)とは、頂点数 $3$ 以上のグラフ $G$ で独立数 $\alpha(G)$ が頂点連結度 $\kappa(G)$ 以下なら $G$ は Hamilton 閉路をもつ、という定理で、V. Chvátal と P. Erdős が 1972 年に示した。最長の閉路の外に頂点が残ったとすると、外の成分に隣接する閉路上の頂点は連結度以上の個数あり、それらの次の頂点と外の成分の頂点が大きすぎる独立集合をなす、という議論で証明される。全頂点に隣接する頂点を加えると、$\alpha(G)\le\kappa(G)+1$ なら Hamilton 路をもつことが従う。Dirac や Ore の次数の条件と違い、最小次数が頂点数の半分より小さいグラフにも使える。
前提知識: Hamilton閉路, 連結度(グラフ), 独立集合
Chvátal–Erdősの定理(Chvátal–Erdős theorem)は、頂点数 $3$ 以上のグラフ $G$ で独立数 $\alpha(G)$ が頂点連結度 $\kappa(G)$ 以下なら、$G$ は Hamilton閉路 をもつ、という定理である。V. Chvátal と P. Erdős が 1972 年に示した。
Diracの定理(Hamilton閉路) や Oreの定理(Hamilton閉路) は、頂点の次数が大きいことを仮定する。これに対して Chvátal–Erdős の定理は、「互いに隣り合わない頂点を多くは選べない」($\alpha$ が小さい)ことと「少ない頂点を除いてもばらばらにならない」($\kappa$ が大きい)ことの比べ合いだけを仮定する。$\kappa(G)\le\delta(G)$ なので次数も少しは大きくなければならないが、$\delta(G)$ が $n/2$ よりずっと小さくても使える(ex-ce-rook)。証明は、最長の閉路の外に頂点が残ったとして、その外の部分に隣接する閉路上の頂点の「次の頂点」を集めると、大きすぎる独立集合ができる、という 1 段落の議論である。
この記事では、定理を証明し、Hamilton 路についての系、例、仮定が外せないことを示す例を述べる。
グラフは有限の単純無向グラフ $G=(V,E)$ とし、$n=|V|$ と書く。閉路・道・Hamilton 閉路・Hamilton 路は Hamilton閉路 の定義「Hamilton閉路とHamilton路」の意味で使う。閉路は長さ $3$ 以上なので、Hamilton 閉路があれば $n\ge3$ である。頂点 $v$ の隣接頂点の集合を $N(v)$、最小次数を $\delta(G)$ と書く。
証明の中心は、最長の閉路の外にある連結成分についての次の補題である。
$C$ を $G$ の最長の閉路とし、$C$ が $G$ のすべての頂点を通らないとする。$G-V(C)$ の連結成分を 1 つとって $H$ とし、$C$ の頂点のうち $H$ のある頂点と隣接するものの集合を $N_C(H)$ と書く。このとき、次が成り立つ。
$H$ は連結なので、$H$ の 2 頂点 $a,b$($a=b$ でもよい)を結ぶ $H$ の中の道 $P$ がある。
1。 $x$ と $x^+$ がともに $N_C(H)$ に属するとし、$x$ が $a\in V(H)$ と、$x^+$ が $b\in V(H)$ と隣接するとする。$C$ から辺 $xx^+$ を除き、代わりに $x,a,\dots,b,x^+$(途中は $P$)をつなぐと、$C$ のすべての頂点と $P$ の頂点(1 個以上)を通る閉路ができる。$H$ の頂点は $C$ の上にないので、これは $C$ より長い閉路であり、$C$ が最長であることに反する。後半は $N_C(H)$ の定義そのものである。
2。 1 により $x^+,y^+\notin N_C(H)$ で、$x,y\in N_C(H)$ なので、$y^+\ne x$、$x^+\ne y$ である。$x\ne y$ なので $x^+\ne y^+$ である。そこで $C$ の頂点は、交わらない 2 つの部分 $C[x^+,y]$ と $C[y^+,x]$ に分かれる。$x^+$ と $y^+$ が隣接するとして矛盾を導く。$x$ が $a\in V(H)$ と、$y$ が $b\in V(H)$ と隣接するとし、$P$ を $a$ から $b$ への $H$ の中の道とする。次の閉路を考える。
$G$ を頂点数 $n\ge3$ のグラフとする。$\alpha(G)\le\kappa(G)$ なら、$G$ は Hamilton 閉路をもつ。
$G$ が完全グラフなら、$n\ge3$ なので頂点を任意の順に並べたものが Hamilton 閉路である。以下、$G$ は完全グラフでないとする。
連結度は 2 以上で、閉路がある。 隣接しない 2 頂点があるので $\alpha(G)\ge2$ であり、仮定から $\kappa(G)\ge2$ である。$\delta(G)\ge\kappa(G)\ge2$ なので、$G$ の最長の道 $v_0,\dots,v_\ell$ をとると、$v_0$ のすべての隣接頂点は道の上にある(外に隣接頂点 $w$ があれば $w,v_0,\dots,v_\ell$ がより長い道になる)。$v_0$ は $v_1$ 以外にも隣接頂点 $v_j$($j\ge2$)をもつので、$v_0,v_1,\dots,v_j,v_0$ は閉路である。よって $G$ には閉路があり、その中に最長のもの $C$ がある。
最長の閉路がすべての頂点を通ることを示す。 通らないとして矛盾を導く。$G-V(C)$ の連結成分 $H$ を 1 つとり、$h\in V(H)$ を選ぶ。lem-ce-component の記号で $N:=N_C(H)$ とおく。
まず $|N|\ge\kappa(G)$ を示す。$C$ の上に $N$ に属さない頂点があることを確かめる。$N$ が $C$ の頂点すべてなら、$x\in N$ について $x^+\in N$ となり、lem-ce-component の 1 に反するからである。その頂点を $w$ とする。$G-N$ で $h$ と $w$ を結ぶ道があったとすると、その道で $H$ の外にある最初の頂点 $u$ は、直前の $H$ の頂点と隣接している。$u$ が $C$ の上になければ $u$ は $G-V(C)$ で $H$ とつながり $H$ に属するはずなので、$u$ は $C$ の上にあり、したがって $u\in N$ である。これは道が $G-N$ の中にあることに反する。よって $G-N$ は連結でない。$G$ は $\kappa(G)$-連結なので、$\kappa(G)$ 個未満の頂点を除いても連結である。したがって $|N|\ge\kappa(G)$ である。
次に、集合 $I:=\{x^+:x\in N\}\cup\{h\}$ を考える。lem-ce-component の 2 により、$x\mapsto x^+$ は $N$ の上で単射で、$I$ のうち $x^+$ の形の頂点どうしは隣接しない。同じ補題の 1 により、$x^+$ は $H$ の頂点 $h$ と隣接しない。$h$ は $C$ の上にないので $x^+$ と異なる。よって $I$ は独立集合で、
$$
\alpha(G)\ge|I|=|N|+1\ge\kappa(G)+1
$$
となる。これは仮定 $\alpha(G)\le\kappa(G)$ に反する。よって $C$ は Hamilton 閉路である。$\square$
証明が使ったのは「$C$ が最長」ということだけで、$C$ の外の成分 $H$ に隣接する頂点の個数を連結度で下から抑え、その次の頂点たちと $H$ の頂点で独立集合を作っている。$\kappa(G)$ が $N$ の大きさを保証し、$\alpha(G)$ がそれを許さない、という対比が定理の形にそのまま現れている。
証明は Hamilton 閉路を実際に見つける手順にもなる。最長の閉路を探す必要はない。lem-ce-component の証明は、1 または 2 が成り立たない箇所を見つければ、$C$ より長い閉路を具体的に作る。1 と 2 がともに成り立てば、prf-ce-main の後半の議論は $C$ が最長であることを使わずに通り、$\kappa(G)+1$ 個の頂点からなる独立集合 $I$ を与える。そこで、まず極大な道(どちらの端からも延ばせない道)から prf-ce-main の前半のように閉路を 1 つ作り、閉路がすべての頂点を通るまで「長い閉路を作る」か「独立集合 $I$ を作る」かを繰り返す。閉路の長さは毎回 1 以上増えるので、繰り返しは $n$ 回以下で終わる。各回の操作は、成分を求め、隣接関係と道を調べるだけなので、頂点数の多項式の時間でできる。$G$ が完全グラフでなく $\alpha(G)\le\kappa(G)$ なら、$\delta(G)\ge2$ なので最初の閉路が作れ、独立集合 $I$ は現れないので、手順は Hamilton 閉路で終わる。手順そのものは $\alpha(G)$ や $\kappa(G)$ の値を使わない。
全頂点に隣接する頂点を 1 つ加えると、連結度が 1 増え、独立数は変わらない。これを使うと、条件を 1 だけ緩めて Hamilton 路が得られる。
$G$ を頂点数 $n\ge2$ のグラフとする。$\alpha(G)\le\kappa(G)+1$ なら、$G$ は Hamilton 路をもつ。
$G$ に新しい頂点 $u$ を加え、$u$ を $G$ のすべての頂点と結んだグラフを $G^*$ とする。連結度(グラフ) の命題「全頂点へ隣接する新頂点の追加」により $\kappa(G^*)=\kappa(G)+1$ である。$G^*$ の独立集合で $u$ を含むものは $\{u\}$ だけで、$u$ を含まないものは $G$ の独立集合なので、$\alpha(G^*)=\max\{1,\alpha(G)\}=\alpha(G)$ である。よって $\alpha(G^*)\le\kappa(G^*)$ で、$G^*$ の頂点数は $n+1\ge3$ だから、thm-ce-main により $G^*$ は Hamilton 閉路をもつ。その閉路から $u$ と $u$ に接する 2 本の辺を除くと、$G$ のすべての頂点を通る道が残る。$\square$
$m\ge2$ とし、部の大きさが $m$ と $\ell$($\ell\ge m$)の 完全二部グラフ $K_{m,\ell}$ を考える。異なる部の頂点はつねに隣接するので、独立集合は 1 つの部に含まれ、$\alpha(K_{m,\ell})=\ell$ である。大きさ $m$ の部を除くと $\ell\ge2$ 個の孤立点が残るので $\kappa\le m$ である。$m$ 個未満の頂点を除いても両方の部に頂点が残り、異なる部の 2 頂点は隣接し、同じ部の 2 頂点は他方の部の頂点を通じて結ばれるので、残りは連結である。よって $\kappa(K_{m,\ell})=m$ である。
$a\ge2$ とし、頂点集合を $\{1,\dots,a\}^2$、$(i,j)$ と $(k,l)$ が隣接するのは $i=k$ または $j=l$(ただし同じ頂点でない)のときとするグラフを $R_a$ とする(チェス盤の $a\times a$ の升目で、ルークが 1 手で動ける升目を結んだもの)。
独立数は $a$。 独立集合は各行に高々 1 頂点しか含まないので $\alpha(R_a)\le a$ で、対角線 $\{(i,i)\}$ は独立集合である。
連結度は $a$ 以上。 $n=a^2>a$ である。$S$ を $a-1$ 個以下の頂点の集合とし、$S$ に属さない 2 頂点 $(i,j)$、$(k,l)$ をとる。$i=k$ または $j=l$ なら隣接している。そうでなければ、各列 $c$ について $(i,j)$ から $(k,l)$ への道 $P_c$ を、$c=j$ なら $(i,j),(k,j),(k,l)$、$c=l$ なら $(i,j),(i,l),(k,l)$、それ以外なら $(i,j),(i,c),(k,c),(k,l)$ と定める。$P_c$ の端点以外の頂点は列 $c$ にあるので、$a$ 本の道の内部は互いに交わらない。$|S|\le a-1$ なので、内部が $S$ と交わらない $P_c$ が少なくとも 1 本あり、2 頂点は $R_a-S$ の中で結ばれる。よって $R_a$ は $a$-連結で、$\kappa(R_a)\ge a=\alpha(R_a)$ である。
thm-ce-main により $R_a$ は Hamilton 閉路をもつ。なお、上の $a$ 本の道に、行 $r\ne i,k$ を通る $a-2$ 本の道 $(i,j),(r,j),(r,l),(k,l)$ を加えた $2a-2$ 本も内部が互いに交わらないので、同じ議論で $\kappa(R_a)\ge2a-2=\delta(R_a)$ となり、$\kappa(R_a)=2a-2$ である(下の表の $\kappa(R_3)=4$)。$a=3$ では $n=9$、どの頂点の次数も $4<9/2$ なので Dirac の条件は成り立たず、隣接しない 2 頂点の次数の和も $8<9$ なので Ore の条件も成り立たない。
次の表は、いくつかのグラフで 3 つの十分条件を比べたものである($n$ は頂点数)。
| グラフ | $n$ | $\delta$ | $\alpha$ | $\kappa$ | Dirac($\delta\ge n/2$) | Ore | Chvátal–Erdős | Hamilton 閉路 |
|---|---|---|---|---|---|---|---|---|
| $K_{3,3}$ | 6 | 3 | 3 | 3 | 成り立つ | 成り立つ | 成り立つ | ある |
| $R_3$ | 9 | 4 | 3 | 4 | 成り立たない | 成り立たない | 成り立つ | ある |
| 閉路 $C_6$ | 6 | 2 | 3 | 2 | 成り立たない | 成り立たない | 成り立たない | ある |
| Petersen グラフ | 10 | 3 | 4 | 3 | 成り立たない | 成り立たない | 成り立たない | ない |
3 行目のように、Chvátal–Erdős の条件は Hamilton 閉路をもつための必要条件ではない。$C_n$($n\ge6$)は $\alpha=\lfloor n/2\rfloor\ge3>2=\kappa$ だが Hamilton 閉路そのものである。4 行目の値は、独立集合 の例「Petersen グラフの独立数」と、$\kappa\le\delta=3$ による。Petersen グラフが Hamilton 閉路をもたないことは Petersenグラフ の定理「Petersen グラフは Hamilton 閉路をもたない」である。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $n\ge3$ | $K_2$ | $\alpha=\kappa=1$ だが、Hamilton 閉路をもたない |
| $\alpha(G)\le\kappa(G)$($\alpha\le\kappa+1$ に緩める) | $K_{m,m+1}$($m\ge2$) | $\alpha=m+1=\kappa+1$ だが、Hamilton 閉路をもたない |
| $\alpha(G)\le\kappa(G)+1$(cor-ce-path の仮定を $\alpha\le\kappa+2$ に緩める) | $K_{m,m+2}$($m\ge1$) | $\alpha=m+2=\kappa+2$ だが、Hamilton 路をもたない |
1 行目:$K_2$ は 1 本の辺で、独立集合は 1 頂点以下なので $\alpha=1$、連結度(グラフ) により $\kappa(K_2)=1$ である。頂点数が $2$ なので閉路をもたない。2 行目:ex-ce-bipartite による。3 行目:$m\ge2$ では ex-ce-bipartite と同じ議論で $\alpha=m+2$、$\kappa=m$ であり、$m=1$ では $K_{1,3}$ の $\alpha=3$、$\kappa=1$(中心を除くと 3 つの孤立点)である。二部グラフの道では 2 つの部の頂点が交互に現れるので、2 つの部の頂点の個数の差は $1$ 以下である。部の大きさが $m$ と $m+2$ なので Hamilton 路はない。
定理は V. Chvátal と P. Erdős の 1972 年の論文 CE72 による。BM76 は演習 9.4.3(p. 151)で、最長の閉路 $C$ の外の成分(同書の言葉で $C$ の「橋」)についての補題を示させ、そこから「$\alpha\le\kappa$ なら Hamilton」を導かせる形で、この定理を Chvátal と Erdős に帰している。同書の演習は頂点数の条件を書いていないが、$K_2$ が示すように $n\ge3$ が要る(rem-ce-counterexamples)。
一般のグラフで独立数を求める問題は NP 困難である(独立集合 の注意「最大独立集合を求める問題」)。そのため、定理を使うときは、$\alpha$ の上界と $\kappa$ の下界を別々に示すことが多い。ex-ce-rook では、行ごとに 1 頂点という数え方で $\alpha$ を上から、内部の交わらない $a$ 本の道で $\kappa$ を下から抑えた。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する