§D2.12マッチング・彩色・平面グラフ

証明. （増加道があれば最大でない）$M$-増加道$P$を$u_0e_1u_1e_2\cdots e_{2k+1}u_{2k+1}$とする。両端$u_0,u_{2k+1}$は$M$-非飽和で、$e_1,e_3,\dots,e_{2k+1}$が非マッチング辺、$e_2,e_4,\dots,e_{2k}$がマッチング辺である。$M':=M\triangle E(P)$とおくと、$M'$は$P$上でマッチング辺と非マッチング辺を入れ替えたものである。$P$の内部の各頂点$u_i$（$1\le i\le 2k$）は、$M$でちょうど一本のマッチング辺（$P$上の）に接していたのが、$M'$でもちょうど一本（$P$上の隣の辺）に接する。両端$u_0,u_{2k+1}$は$M$で非飽和、$M'$でちょうど一本に接する。$P$外の頂点の接続は不変。ゆえに$M'$でも各頂点は高々一本の辺に接し、$M'$はマッチングである。$P$は非マッチング辺$k+1$本・マッチング辺$k$本を含むので$|M'|=|M|-k+(k+1)=|M|+1$。よって$M$は最大でない。

（最大でなければ増加道がある）$M$が最大でないとし、$|M^*|>|M|$なるマッチング$M^*$をとる。対称差$H:=M\triangle M^*$を辺集合とする部分グラフを考える。各頂点は$M$の辺に高々一本、$M^*$の辺に高々一本しか接しないから、$H$における次数は高々$2$である。ゆえに$H$の各連結成分は道または閉路であり、$H$の辺は$M$と$M^*$に交互に属する（同じマッチングの二辺は端点を共有しないため隣り合えない）。閉路成分は交互だから長さが偶数で、$M$の辺と$M^*$の辺を同数含む。いま$|M^*|>|M|$、すなわち$H$全体で$M^*$の辺が$M$の辺より多いから、$M^*$の辺を$M$の辺より多く含む成分が存在する。それは閉路ではありえず、両端が$M^*$の辺で終わる道$Q$である。$Q$の両端点は$M^*$の辺に接するが$M$の辺には接しない（$Q$内で端点に隣接する$M$辺がない）から$M$-非飽和であり、$Q$の辺は$M$と$M^*$に交互に属するので$Q$は$M$-増加道である。▨

証明. （必要性）$X$を飽和するマッチング$M$があるとする。各$x\in X$をその相手$M(x)\in Y$に写す対応は$S\subseteq X$上で単射であり（相異なる頂点は相異なる相手をもつ）、像は$N(S)$に含まれる。ゆえに$|N(S)|\ge|S|$。

（十分性）$|X|$に関する帰納法で示す。$|X|=0$のときは空マッチングが$X$を飽和する。$|X|=1$のとき、ホールの条件$|N(\{x\})|\ge 1$より$x$に隣接する$y$があり、$\{xy\}$が$X$を飽和する。$|X|\ge 2$とし、より小さい部集合に対して主張が成り立つと仮定する。次の二つの場合に分ける。

場合 1: すべての空でない真部分集合$S\subsetneq X$で$|N(S)|\ge|S|+1$（余裕がある）. 任意の$x\in X$をとり、$N(\{x\})\ne\varnothing$より$y\in N(\{x\})$を一つ選んで辺$xy$をマッチングに入れる。$G$から$x,y$を除いたグラフで$X':=X\setminus\{x\}$を考える。任意の$S\subseteq X'$について、$G$での近傍$N(S)$から$y$を除いた高々一つ分しか減らないから$|N_{G-y}(S)|\ge |N_G(S)|-1\ge (|S|+1)-1=|S|.$ホールの条件が保たれるので、帰納法の仮定により$X'$を飽和するマッチングがとれる。これに$xy$を加えれば$X$を飽和する。

場合 2: ある空でない真部分集合$S_0\subsetneq X$で$|N(S_0)|=|S_0|$（等号がぎりぎり成立）. まず$S_0\cup N(S_0)$が張る部分グラフ$G_0$を考える。任意の$T\subseteq S_0$について、$G_0$での$T$の近傍は$G$でのそれと一致し$N(T)\subseteq N(S_0)$、かつ$|N(T)|\ge|T|$。$|S_0|<|X|$だから帰納法の仮定により$S_0$を飽和するマッチング$M_1$がとれる。

次に、残りの頂点が張る部分グラフ$G_1$（部集合$X\setminus S_0$と$Y\setminus N(S_0)$）を考える。任意の$T\subseteq X\setminus S_0$に対し、$G_1$での近傍は$N_{G_1}(T)=N_G(T)\setminus N(S_0)$である。ここでホールの条件を$S_0\cup T$に適用すると、$N_G(S_0\cup T)=N_G(S_0)\cup N_G(T)$かつ$|N_G(S_0)|=|S_0|$より$|N_{G_1}(T)|=|N_G(S_0\cup T)\setminus N_G(S_0)|\ge |S_0\cup T|-|S_0|=(|S_0|+|T|)-|S_0|=|T|.$（$S_0$と$T$は互いに素なので$|S_0\cup T|=|S_0|+|T|$。）よって$G_1$でホールの条件が成り立ち、$|X\setminus S_0|<|X|$だから帰納法の仮定により$X\setminus S_0$を飽和するマッチング$M_2$がとれる。$M_1$と$M_2$は頂点集合が互いに素なので$M_1\cup M_2$はマッチングであり、$X=S_0\cup(X\setminus S_0)$全体を飽和する。▨

証明. 部集合を$X,Y$とする。弱い向き（最小頂点被覆$\ge$最大マッチング）はすぐわかる：マッチング$M$の辺は互いに端点を共有しないから、それらを覆うにはマッチング辺ごとに相異なる頂点が少なくとも一つ要り、任意の頂点被覆は$\ge|M|$個の頂点をもつ。したがって最小頂点被覆$\ge$最大マッチング。

等号を示すため、最大マッチング$M$（$|M|=m$）から大きさ$m$の頂点被覆を構成する。$X$の$M$-非飽和頂点全体を$U$とし、$U$の頂点から$M$-交互道で到達できる頂点全体を$Z$とする（交互道は$U$の頂点から非マッチング辺で出発し、以後マッチング辺・非マッチング辺を交互にたどる）。定義により、$Z\cap X$の頂点はマッチング辺で（または始点として）到達され、$Z\cap Y$の頂点は非マッチング辺で到達される。ここで$K:=(X\setminus Z)\cup(Y\cap Z)$とおく。

$K$は頂点被覆である. 辺$xy$（$x\in X,\ y\in Y$）が$K$に覆われないと仮定すると、$x\notin X\setminus Z$すなわち$x\in Z$、かつ$y\notin Y\cap Z$すなわち$y\notin Z$である。

• $xy\in M$の場合：$x\in Z\cap X$が始点$U$に属せば$x$は非飽和なので$xy\in M$に反する。$x\in Z\cap X\setminus U$なら、$x$はマッチング辺で到達されているから、$x$の唯一のマッチング相手は$Z$に属する。その相手は$y$（$xy\in M$）だから$y\in Z$、矛盾。
• $xy\notin M$の場合：$x\in Z\cap X$から非マッチング辺$xy$に沿って交互道を延長でき$y\in Z$、矛盾。

いずれも矛盾するので、すべての辺は$K$に覆われる。

$|K|=m$. 二つの観察を用いる。

(i)$Y\cap Z$の各頂点は$M$-飽和である。もし$y\in Y\cap Z$が非飽和なら、$U$（非飽和）から$y$（非飽和）への$M$-交互道は$M$-増加道となり、$M$の最大性（定理 1.2）に反する。ゆえに$y$はマッチング相手$M(y)\in X$をもち、$y\in Z$からマッチング辺で$M(y)$に到達できるので$M(y)\in X\cap Z$、したがって$M(y)\notin K$。

(ii)$X\setminus Z$の各頂点$x$は$M$-飽和である（非飽和なら$x\in U\subseteq Z$となり$x\notin Z$に反する）。相手$M(x)\in Y$について、もし$M(x)\in Y\cap Z$なら、そのマッチング辺により$x\in Z$となって矛盾。ゆえに$M(x)\in Y\setminus Z$、したがって$M(x)\notin K$。

(i)(ii) により、$K$の各頂点をそのマッチング辺に対応させる写像を定める。$X\setminus Z$の頂点は$X$-側端点が$X\setminus Z$にあるマッチング辺へ、$Y\cap Z$の頂点は$X$-側端点が$X\cap Z$にあるマッチング辺へ移る。これら二種のマッチング辺は$X$-側端点が別（$X\setminus Z$と$X\cap Z$）だから相異なり、$K$の相異なる頂点は相異なる$M$の辺へ単射に写る。ゆえに$|K|\le|M|=m$。

以上より、頂点被覆$K$が存在して$|K|\le m$。弱い向きから任意の頂点被覆は$\ge m$なので、最小頂点被覆は$m$に等しく、$=|K|=$最大マッチングである。▨

証明. 頂点に任意の順序$v_1,v_2,\dots,v_n$を与え、$i=1,2,\dots,n$の順に、$v_i$に対して「すでに彩色済みの隣接頂点が使っていない最小の色」を割り当てる（貪欲彩色）。$v_i$を塗る時点で、その隣接頂点は高々$\deg(v_i)\le\Delta(G)$個であり、それらが使う色は高々$\Delta(G)$種類である。ゆえに色の集合$\{1,2,\dots,\Delta(G)+1\}$には必ず未使用の色があり、$v_i$を塗れる。各頂点は塗る時点で隣接済み頂点と異なる色をもつので、得られる彩色は真の彩色である。使う色は$\Delta(G)+1$種以下だから$\chi(G)\le\Delta(G)+1$。▨

証明. (a)$\Leftrightarrow$(b).$\chi(G)\le 2$なら$2$-彩色$c\colon V\to\{1,2\}$があり、$V_1:=c^{-1}(1)$,$V_2:=c^{-1}(2)$はともに独立集合で、すべての辺は$V_1$と$V_2$をまたぐから$G$は二部（辺が無いなら$\chi(G)=1$でも二部）。逆に二部分割$V=X\sqcup Y$があれば、$X$に色$1$、$Y$に色$2$を与えると真の$2$-彩色になり$\chi(G)\le 2$。

§D2.7 定理 5.3により、(b) と (c) は同値です。▨

証明. 辺数$E$に関する帰納法で示します。位相的入力として、ジョルダン曲線定理（平面上の単純閉曲線は平面を二つの連結成分に分けること）と、その平面埋め込みへの帰結である「閉路上の辺を削除すると、その辺に接する相異なる二面が一つに併合され、それ以外の面は変わらないこと」を認めて用います。

$G$が閉路をもたない場合、連結だから$G$は木であり$E=V-1$である。木の平面埋め込みは平面を分割せず面はただ一つ（外面のみ）で$F=1$。ゆえに$V-E+F=V-(V-1)+1=2$。

$G$が閉路をもつ場合、その閉路上の辺$e$を一つとる。選択済み埋め込みにおける閉路の像は単純閉曲線であり、上で認めた位相的入力により、$e$は相異なる二面に接し、$e$を除くとこの二面だけが一つに併合される。したがって面数は$1$減る。また、$e$は閉路上の辺だから除いても連結性は保たれる。$G-e$は連結な平面グラフで、辺数$E-1$、面数$F-1$、頂点数$V$である。帰納法の仮定により$V-(E-1)+(F-1)=2\quad\Longrightarrow\quad V-E+F=2.$▨

証明. まず$G$が連結な場合を示す。平面埋め込みをとり、$E\le 2$ならば$3V-6\ge 3>E$かつ$2V-4\ge 2\ge E$なので両方の評価が成立する。以下では$E\ge 3$とする。各面$f$の境界の長さ（境界を一周する閉じた歩道でたどる辺の延べ本数、橋は二回数える）を$\ell(f)$とする。各辺はちょうど二つの面の境界に一回ずつ（橋なら同じ面に二回）現れるので$\sum_{f}\ell(f)=2E.$$G$は単純で$V\ge 3$,$E\ge 3$だから、各面の境界の長さは$\ell(f)\ge 3$である（ループ・多重辺がないため長さ$1,2$の面境界は生じない）。ゆえに$3F\le\sum_f\ell(f)=2E$、すなわち$F\le \tfrac{2}{3}E$。オイラーの公式(定理 3.2)$F=2-V+E$を代入して$2-V+E\le\tfrac{2}{3}E\ \Longrightarrow\ 6-3V+3E\le 2E\ \Longrightarrow\ E\le 3V-6.$二部の場合は奇閉路がない（命題 2.3）ので最短閉路長が$4$以上、各面の境界の長さは$\ell(f)\ge 4$。同様に$4F\le 2E$、$F\le\tfrac{1}{2}E$、$2-V+E\le\tfrac12 E$から$E\le 2V-4$。

$G$が非連結で、連結成分が$c$個あるとする。各成分の平面描画を互いに交わらない小円板内に配置し、それぞれ一つの頂点が円板の外周に接するようにとる。隣り合う円板の選んだ頂点を外側から曲線で結べば、既存辺と交差せずに$c-1$本の辺を加えられる。端点は異なる成分に属していたので既存辺はなく、単純性も保たれる。こうして得た$G'$は$G$と同じ$V$頂点をもち、$E'=E+c-1$辺の連結単純平面グラフである。したがって一般には

となる。

$G$が二部である場合には、各成分の二部配色を独立に選べる。成分を一本の新しい辺で結ぶたびに、必要なら一方の成分の二色を入れ替えて、新しい辺の両端が異なる色になるようにする。この操作は既存辺の配色も平面描画も変えないので、上で得る$G'$は二部グラフのままである。連結な二部グラフに対する評価を$G'$に適用すると

したがって$E\le 2V-4$を得る。

応用.$K_5$は$V=5$,$E=\binom{5}{2}=10$で、$3V-6=9<10$。ゆえに$E\le 3V-6$を破り平面的でない。$K_{3,3}$は二部で$V=6$,$E=9$、$2V-4=8<9$。ゆえに二部版の評価を破り平面的でない。▨

証明. 頂点数$V$に関する強帰納法で「頂点数$n$の平面的グラフは$6$-彩色可能」を示す。$n\le 6$のときは各頂点に相異なる色を与えれば高々$6$色で真に塗れる。

$n\ge 7$とし、$n$未満で主張が成り立つと仮定する。$G$を頂点数$n$の単純平面的グラフとする。$V\ge 3$だから系 3.4より$E\le 3V-6$。握手補題$\sum_v\deg(v)=2E$（辺一本が両端点で二回数えられる、既習）を使うと$\sum_{v}\deg(v)=2E\le 6V-12<6V,$よって平均次数は$6$未満であり、$\deg(v)\le 5$なる頂点$v$が少なくとも一つ存在する（全頂点が次数$\ge 6$なら$\sum\deg\ge 6V$に反する）。この$v$を除いた$G-v$は頂点数$n-1$の平面的グラフだから、帰納法の仮定により$6$-彩色できる。$v$の隣接頂点は高々$5$個で、それらが使う色は高々$5$種類なので、$6$色のうち少なくとも一色が$v$に使える。その色を$v$に与えれば$G$の$6$-彩色が得られる。▨