§E13.13二部マッチングと Kőnig の定理

証明. 両端点$v_0$と$v_k$は$M$-非飽和であるから、$v_0$に接する辺$v_0v_1$と$v_k$に接する辺$v_{k-1}v_k$はいずれも$M$に属さない。$P$は$M$-交互道であるから、辺$v_{i-1}v_i$が$M$に属するかどうかは$i$とともに交互に入れ替わる。最初の辺$v_0v_1$が$M$に属さないので、$v_{i-1}v_i$が$M$に属することと$i$が偶数であることは同値である。最後の辺$v_{k-1}v_k$が$M$に属さないので$k$は奇数である。

$1\le i\le k$のうち$i$が奇数であるものは$(k+1)/2$個、偶数であるものは$(k-1)/2$個であるから、$M$に属さない辺は$(k+1)/2$本、$M$に属する辺は$(k-1)/2$本である。▨

証明.$K$を$H$の連結成分とする。$K$の頂点は有限個であるから、$K$に含まれる道の長さは有界であり、長さが最大である道$P:\ u_0,u_1,\dots,u_r$が存在する。

$r=0$の場合を先に扱う。$u_0$に隣接する頂点$w$が存在すれば$u_0,w$が長さ$1$の道となって最大性に反するので、$u_0$の次数は$0$である。$K$は連結であるから$K$は$u_0$だけからなり、(1)が成り立つ。

以下$r\ge1$とする。$u_0$に隣接する頂点$w$が$P$に現れないと仮定すると、$w,u_0,u_1,\dots,u_r$が$P$より長い道となって最大性に反する。よって$u_0$に隣接する頂点はすべて$P$に現れる。同じ理由で、$u_r$に隣接する頂点もすべて$P$に現れる。また、$0<i<r$を満たす$u_i$は$u_{i-1}$と$u_{i+1}$に隣接し、次数が$2$以下であるから、これ以外の頂点には隣接しない。

$u_0$が$u_1$以外の頂点に隣接しない場合を考える。$u_r$が$u_{r-1}$以外の頂点に隣接すると仮定すると、その頂点は$P$に現れるので$u_j$（$0\le j\le r-2$）と書くことができる。$j=0$ならば$u_0$が$u_1$以外の頂点に隣接することになって仮定に反する。$0<j$ならば$u_j$は$u_{j-1}$、$u_{j+1}$および$u_r$の三頂点に隣接し、次数が$3$になって仮定に反する。よって$u_r$も$u_{r-1}$以外の頂点に隣接しない。したがって$P$のどの頂点も$P$の辺以外の辺に接しない。$K$は連結であるから、$K$の頂点はすべて$P$に現れ、$K$の辺は$P$の辺だけである。よって(1)が成り立つ。

$u_0$が$u_1$以外の頂点$u_i$に隣接する場合を考える。自己ループが無いので$i\ne0$であり、$i\ne1$であるから$i\ge2$である。$i<r$と仮定すると、$u_i$は$u_{i-1}$、$u_{i+1}$および$u_0$の三頂点に隣接して次数が$3$になり、仮定に反する。よって$i=r$であり、$r\ge2$である。このとき$u_0,u_1,\dots,u_r,u_0$は閉路である。この閉路に現れる各頂点は既に二つの頂点に隣接しているので、次数が$2$以下であることからこれ以外の頂点には隣接しない。$K$は連結であるから、$K$の頂点はすべてこの閉路に現れ、$K$の辺はこの閉路の辺だけである。よって(2)が成り立つ。▨

証明. 増加道が存在すれば最大でないこと。$M$-増加道$P:\ v_0,v_1,\dots,v_k$をとる。補題 1.3により$k$は奇数であり、$P$の辺のうち$M$に属さないものが$(k+1)/2$本、属するものが$(k-1)/2$本である。$P$の辺集合を$E(P)$と書き、

と置く。$M'$がマッチングであることを示す。頂点$w$をとる。$w$が$P$に現れないならば、$w$に接する$M'$の辺は$w$に接する$M$の辺と同じであるから高々一本である。$w$が$P$の内部の頂点$v_i$（$0<i<k$）であるならば、$w$に接する$P$の辺はちょうど二本$v_{i-1}v_i$と$v_iv_{i+1}$であり、交互性によりそのうち一本が$M$に属し他方が属さない。したがって$M'$では、$M$に属していた方が外れ、属していなかった方が入るので、$w$に接する$P$の辺のうち$M'$に属するものはちょうど一本である。さらに、$P$に現れない辺で$w$に接し$M$に属するものは存在しない。もし存在すれば、$w$は$P$上の$M$の辺と合わせて$M$の二本の辺に接することになり、$M$がマッチングであることに反する。$w$が端点$v_0$または$v_k$であるならば、$w$は$M$-非飽和であるから$M$の辺に接しておらず、$M'$では$P$上の$M$に属さない辺一本だけに接する。以上より$M'$はマッチングである。辺数は

であるから、$M$は最大マッチングではない。

最大でなければ増加道が存在すること。$M$が最大でないとし、$\lvert M'\rvert>\lvert M\rvert$を満たすマッチング$M'$をとる。辺集合

と、$D$の辺の端点全体を頂点集合とする部分グラフ$H$を考える。$H$の各頂点は、$M$の辺に高々一本、$M'$の辺に高々一本しか接しないので、$H$における次数は$1$または$2$である。したがって補題 1.4により、$H$の各連結成分は道または閉路である。また、$H$において同じ頂点に接する二本の辺が同時に$M$に属することはなく、同時に$M'$に属することもないから、道または閉路に沿って辺は$M\setminus M'$と$M'\setminus M$に交互に属する。とくに各成分は$M$-交互道または$M$-交互な閉路である。

閉路成分の長さが偶数であることを示す。閉路を一周すると辺の属する側が一本ごとに入れ替わる。長さが奇数であるとすると、一周して戻ったところで同じ側の二本の辺が一つの頂点に接することになり、その頂点が$M$の二本の辺に接するか$M'$の二本の辺に接することになって、マッチングであることに反する。よって閉路成分の長さは偶数であり、$M$の辺と$M'$の辺を同数含む。$\lvert M'\setminus M\rvert=\lvert M'\rvert-\lvert M\cap M'\rvert>\lvert M\rvert-\lvert M\cap M'\rvert=\lvert M\setminus M'\rvert$であるから、$H$全体では$M'$の辺が$M$の辺より多い。ゆえに$M'$の辺を$M$の辺より多く含む成分が存在し、それは閉路ではなく道である。その道を$Q$とする。$Q$の辺は$M\setminus M'$と$M'\setminus M$に交互に属するので、両者の本数の差は$1$以下である。$Q$は$M'$の辺を$M$の辺より多く含むから、差はちょうど$1$であり、$Q$の長さは奇数で、$Q$の両端の辺はいずれも$M'\setminus M$に属する。

$Q$の端点$w$が$M$-非飽和であることを示す。$w$に接する$H$の辺は$Q$の端の辺ただ一本であり、それは$M'\setminus M$に属する。$w$が$M$に被覆されていると仮定し、その辺を$e\in M$とする。$e$は$H$の辺ではないので$e\in M\cap M'$である。すると$w$は$M'$の二本の辺、すなわち$e$と$Q$の端の辺に接することになり、$M'$がマッチングであることに反する。よって$w$は$M$-非飽和である。もう一方の端点についても同じ議論が成り立つ。

したがって$Q$は両端点が$M$-非飽和である$M$-交互道であり、長さは$1$以上であるから$M$-増加道である。▨

証明. ループ不変条件（§D2.8 定義 1.1）として「$M$はマッチングである」をとる。初期化では$M=\emptyset$がマッチングであるから成り立つ。維持は定理 1.5の証明の前半が与える。すなわち$M$-増加道に沿う入れ替えの結果はマッチングであり、辺数はちょうど$1$増える。

停止性を示す。マッチングの各辺は$X$の相異なる頂点と$Y$の相異なる頂点を用いるから、任意のマッチングの辺数は$\min\{\lvert X\rvert,\lvert Y\rvert\}$以下である。$m=\min\{\lvert X\rvert,\lvert Y\rvert\}$と置き、ループの状態に対して変量$V=m-\lvert M\rvert$を定めると、$V$は非負整数であり、本体を一度実行するたびに$\lvert M\rvert$が$1$増えるので狭義に減少する。§D2.8 命題 1.4により手続きは有限回で停止し、$V$の初期値が$m$であるから反復回数は$m$以下である。

停止時にはループの継続条件が偽であり、$M$-増加道が存在しない。不変条件により$M$はマッチングであるから、定理 1.5により$M$は最大マッチングである。この形の議論が正当性を与えることは§D2.8 定理 1.2による。▨

証明.$M$をマッチング、$C$を頂点被覆とする。$M$の各辺$e$は少なくとも一方の端点を$C$にもつので、その端点の一つを選んで$\psi(e)\in C$と定める。$M$の相異なる二辺は端点を共有しないから、$\psi$は単射である。よって$\lvert M\rvert\le\lvert C\rvert$が成り立つ。$M$を最大マッチング、$C$を頂点数が最小の頂点被覆にとると$\nu(G)\le\tau(G)$を得る。▨

証明. まず$Z$の定義に現れる道の形を確かめる。$u\in U$から出発し最初の辺が$M$に属さない$M$-交互道$u=v_0,v_1,\dots,v_k$をとる。交互性により、辺$v_{i-1}v_i$は$i$が偶数のとき$M$に属し、$i$が奇数のとき$M$に属さない。$u\in X$であり各辺が$X$と$Y$をまたぐので、$v_i$は$i$が偶数のとき$X$に、奇数のとき$Y$に属する。したがって、終点が$Y$に属するときは$k$が奇数で最後の辺は$M$に属さず、終点が$X$に属するときは$k$が偶数で、$k\ge2$ならば最後の辺は$M$に属する。また、この道の始点側の部分列$v_0,\dots,v_j$は再び同じ条件を満たす$M$-交互道であるから、道に現れるすべての頂点は$Z$に属する。

(1)を示す。$x\in Z\cap X$かつ$x\notin U$とする。$x$へ至る上の形の道$v_0,\dots,v_k$をとると、$k$は偶数である。$k=0$ならば$x=u\in U$となって仮定に反するので$k\ge2$であり、最後の辺$v_{k-1}v_k=v_{k-1}x$は$M$に属する。よって$x$は$M$に被覆され、その辺の他方の端点$v_{k-1}$は道上の頂点であるから$Z$に属し、$k-1$が奇数であるから$Y$に属する。

(2)を示す。$y\in Z\cap Y$とし、$y$へ至る上の形の道$P:\ v_0,\dots,v_k$をとる。$k$は奇数であり、最後の辺は$M$に属さない。

$y$が$M$-非飽和であると仮定する。$P$の始点$v_0=u$は$U$に属するので$M$-非飽和であり、$k\ge1$であるから、$P$は両端点がいずれも$M$-非飽和である$M$-交互道、すなわち$M$-増加道である。これは$M$が最大マッチングであることと定理 1.5に反する。よって$y$は$M$に被覆される。

$y$を被覆する$M$の辺を$xy$とする。$x\in X$である。$x$が$P$に現れるならば、上に述べたとおり$x\in Z$である。$x$が$P$に現れないならば、$P$の末尾に辺$yx$を付け加えた列$v_0,\dots,v_k,x$は頂点がすべて相異なるので道であり、$P$の最後の辺が$M$に属さず$yx$が$M$に属するので交互性も保たれる。よってこの道は$Z$の定義の条件を満たし、$x\in Z$である。いずれの場合も$x\in Z\cap X$となる。

(3)を示す。$x\in Z\cap X$かつ$xy\in E\setminus M$とする。$x$へ至る上の形の道$P:\ v_0,\dots,v_k$をとると$k$は偶数である。$y$が$P$に現れるならば$y\in Z$である。$y$が$P$に現れないならば、列$v_0,\dots,v_k,y$は道である。$k=0$のときこの道の最初の辺は$xy$であり$M$に属さないので条件を満たし、$k\ge2$のとき$P$の最後の辺は$M$に属し$xy$は属さないので交互性が保たれる。いずれの場合も$y\in Z$である。▨

証明. 最大マッチング$M$をとる。$U$と$Z$を補題 3.1のとおりに定め、

と置く。$X$と$Y$は交わらないので、この合併は交わらない二つの集合の合併である。

主張1:$C$は頂点被覆である。辺$xy\in E$（$x\in X$、$y\in Y$）をとり、$x\notin C$かつ$y\notin C$であると仮定する。$x\notin X\setminus Z$より$x\in Z$であり、$y\notin Y\cap Z$より$y\notin Z$である。

$xy\notin M$の場合、補題 3.1 (3)により$y\in Z$となり、$y\notin Z$に反する。

$xy\in M$の場合、$x$は$M$に被覆されるので$x\notin U$である。補題 3.1 (1)により、$x$を被覆する$M$の辺の他方の端点が$Z$に属する。$M$はマッチングであるから$x$を被覆する$M$の辺は$xy$ただ一本であり、その他方の端点は$y$である。よって$y\in Z$となり、$y\notin Z$に反する。

いずれの場合も矛盾するので、$E$のすべての辺は少なくとも一方の端点を$C$にもつ。よって$C$は頂点被覆である。

主張2:$\lvert C\rvert\le\lvert M\rvert$である。まず$C$の各頂点が$M$に被覆されることを示す。$x\in X\setminus Z$が$M$-非飽和であるとすると$x\in U$であり、長さ$0$の道により$x\in Z$となって$x\notin Z$に反する。よって$X\setminus Z$の頂点は$M$に被覆される。$Y\cap Z$の頂点が$M$に被覆されることは補題 3.1 (2)による。

そこで、$C$の各頂点$v$に対し、$v$を被覆する$M$の辺$\varphi(v)$を対応させる。$M$はマッチングであるから、$v$を被覆する$M$の辺はただ一本であり、$\varphi$は矛盾なく定まる。$\varphi$が単射であることを示す。$\varphi(v)=\varphi(v')=e$かつ$v\ne v'$とすると、$v$と$v'$はともに$e$の端点であるから、一方が$X$に、他方が$Y$に属する。$X$に属する方を$x$、$Y$に属する方を$y$とすると、$x\in X\setminus Z$かつ$y\in Y\cap Z$かつ$xy=e\in M$である。ところが補題 3.1 (2)により、$y$を被覆する$M$の辺の他方の端点は$Z$に属するので$x\in Z$となり、$x\notin Z$に反する。よって$\varphi$は単射であり$\lvert C\rvert\le\lvert M\rvert$が成り立つ。

結論。$M$は最大マッチングであるから$\lvert M\rvert=\nu(G)$である。$C$は頂点被覆であるから$\tau(G)\le\lvert C\rvert$である。主張2 と命題 2.2を合わせると

となり、すべてが等号で結ばれる。よって$\nu(G)=\tau(G)$であり、あわせて$\lvert C\rvert=\lvert M\rvert=\nu(G)$が得られる。▨