Gallai–Edmondsの分解定理

1. $G-v$ のマッチングは $G$ の $v$ を飽和しないマッチングと同じものなので、$\nu(G-v)\le\nu(G)$ であり、等号は $v$ を飽和しない最大マッチングがあるときに限る。$G$ の最大マッチングから $v$ に接続する辺（あれば 1 本）を除けば $G-v$ のマッチングなので $\nu(G-v)\ge\nu(G)-1$ である。
2. $|V(H)|=2k+1$ とすると、どのマッチングも $2k+1$ 個の頂点のうち偶数個しか飽和しないので $\nu(H)\le k$ である。各頂点 $v$ について $H-v$ の完全マッチングは大きさ $k$ で $v$ を飽和しない $H$ の最大マッチングだから、$v\in D(H)$ である。$\square$

要点：各頂点には $M$ の辺と $N$ の辺が高々 1 本ずつ接続する。

どの最大マッチングも飽和しない頂点が高々 1 個であるとする。各頂点 $v$ について $v$ を飽和しない最大マッチング $M_v$ があり、$M_v$ が飽和しないのは $v$ だけなので、$M_v$ は $G-v$ の完全マッチングである。よって $G$ は因子臨界である。
そこで、飽和しない頂点を 2 個以上もつ最大マッチングがあると仮定して矛盾を導く。最大マッチング $M$ と、$M$ で飽和されない相異なる 2 頂点 $u,v$ の組のうち、$G$ での距離 $\operatorname{dist}(u,v)$ が最小のものを選ぶ（$G$ は連結なので距離は有限）。$uv\in E$ なら $M\cup\{uv\}$ がより大きいマッチングになるので、$\operatorname{dist}(u,v)\ge2$ である。$u$ から $v$ への最短の道の 2 番目の頂点を $w$ とすると、$w\neq u,v$、$\operatorname{dist}(u,w)=1$、$\operatorname{dist}(w,v)=\operatorname{dist}(u,v)-1$ である。距離の最小性から $M$ は $w$ を飽和する（さもなければ組 $u,w$ のほうが近い）。
仮定 $D(G)=V$ により $w$ を飽和しない最大マッチングがある。そのうち $|M\cap N|$ が最大のものを $N$ とする。距離の最小性から、$N$ は $u$ と $v$ を飽和する（さもなければ組 $u,w$ か組 $w,v$ のほうが近い）。$H$ を $M\triangle N$ のグラフとする。
$u$ は $N$ で飽和され $M$ で飽和されないので、$u$ の $N$ の辺は $M$ に属さず、$u$ は $H$ で次数 $1$ である。よって $u$ は $H$ の道の成分 $P_u$ の端点で、$u$ での道の辺は $N$ に属する。$P_u$ のもう一方の端点を $x$ とする。$x$ での道の辺が $N$ に属するなら、lem-ge-symdiff の 2 により $x$ は $M$ で飽和されず、$P_u$ は $N$ の辺を $M$ の辺より 1 本多く含むので、lem-ge-symdiff の 3 のマッチング $M\triangle E(P_u)$ は $M$ より大きい。これは $M$ の最大性に反する。したがって $x$ での道の辺は $M$ に属し、$x$ は $N$ で飽和されず、$P_u$ の $M$ の辺と $N$ の辺の本数は等しく、$P_u$ の長さは $2$ 以上の偶数である。
$x\neq w$ と仮定する。$w$ は $M$ で飽和され $N$ で飽和されないので $H$ の道の成分の端点である。$w$ が $P_u$ の上にあれば $w$ は $P_u$ の端点 $u$ か $x$ になるが、どちらでもないので $w\notin P_u$ である。$N':=N\triangle E(P_u)$ は（lem-ge-symdiff の 3 を $M,N$ の役を入れ替えて使うと）$|N|$ と同じ大きさのマッチングで、$w$ を飽和せず、$|M\cap N'|=|M\cap N|+|E(P_u)\cap M|>|M\cap N|$ である。これは $N$ の選び方に反する。よって $x=w$ である。
同じ議論を $v$ に当てると、$v$ を端点とする $H$ の道の成分のもう一方の端点も $w$ である。$H$ の成分は頂点を共有しないので、この成分は $P_u$ であり、その端点は $\{u,w\}=\{v,w\}$ となって $u=v$ を得る。これは矛盾である。$\square$

$\nu:=\nu(G)$ とおく。$a\notin D(G)$ なので lem-ge-basic の 1 により $\nu(G-a)=\nu-1$ である。
$D(G)\subset D(G-a)$：$u\in D(G)$ とし、$u$ を飽和しない $G$ の最大マッチング $M$ をとる。$a\notin D(G)$ なので $M$ は $a$ を飽和する。$M$ から $a$ に接続する辺を除くと、$G-a-u$ の大きさ $\nu-1$ のマッチングになる。よって $\nu(G-a-u)\ge\nu-1=\nu(G-a)$ であり、lem-ge-basic の 1 により $u\in D(G-a)$ である。
$D(G-a)\subset D(G)$：$u\in D(G-a)$ とし、$u\notin D(G)$ と仮定して矛盾を導く。$a\in A(G)$ なので $a$ に隣接する $d\in D(G)$ があり、$d$ を飽和しない $G$ の最大マッチング $M$ をとる。$u\in D(G-a)$ なので、$u$ を飽和しない $G-a$ の最大マッチング $N$（大きさ $\nu-1$）がある。$M$ は $a$ と $u$ を飽和し（$a,u\notin D(G)$）、$N$ はどちらも飽和しない。$H$ を $M\triangle N$ のグラフとすると、$u$ と $a$ はどちらも $H$ の道の成分の端点で、そこでの道の辺は $M$ に属する。$u$ を端点とする成分を $P_u$ とする。

• $P_u$ のもう一方の端点が $a$ のとき：$P_u$ の両端の辺は $M$ に属するので、lem-ge-symdiff の 3 により $M':=M\triangle E(P_u)$ は大きさ $\nu-1$ のマッチングで、$u$ と $a$ を飽和しない。$d$ は $M$ で飽和されないので $P_u$ の端点ではなく、内部の頂点は $M$ と $N$ の両方で飽和されるので、$d\notin P_u$ であり、$M'$ も $d$ を飽和しない。よって $M'\cup\{ad\}$ は $u$ を飽和しない大きさ $\nu$ のマッチングであり、$u\in D(G)$ となって矛盾する。
• $P_u$ が $a$ を含まないとき：もう一方の端点を $x$ とする。$x$ での道の辺が $M$ に属するなら、$P_u$ は $M$ の辺を $N$ の辺より 1 本多く含み、$N\triangle E(P_u)$ は大きさ $\nu$ のマッチングである。$P_u$ は $a$ を含まず $N$ は $a$ を飽和しないので、これは $G-a$ のマッチングであり、$\nu(G-a)=\nu-1$ に反する。したがって $x$ での道の辺は $N$ に属し、$M\triangle E(P_u)$ は大きさ $\nu$ のマッチングで $u$ を飽和しない。$u\in D(G)$ となって矛盾する。

残りの等式：$D(G-a)=D(G)$ と $a\notin D(G)$ から、$v\neq a$ について「$v\notin D(G-a)$ で $G-a$ において $D(G-a)$ の頂点と隣接する」ことは「$v\notin D(G)$ で $G$ において $D(G)$ の頂点と隣接する」ことと同じである。よって $A(G-a)=A(G)\setminus\{a\}$ であり、$C(G-a)=(V\setminus\{a\})\setminus(D(G)\cup A(G)\setminus\{a\})=C(G)$ である。$\square$

$|A|$ についての帰納法による。$A=\emptyset$ なら明らかである。$a\in A$ をとると、lem-ge-stability により $G-a$ の分解は $D(G)$、$A\setminus\{a\}$、$C(G)$ で、$\nu(G-a)=\nu(G)-1$ である。$G-a$ に帰納法の仮定を当てると、$(G-a)-(A\setminus\{a\})=G-A$ について主張が成り立つ。$\square$

段 1（$G-A$ の形）：$D$ の頂点の隣接頂点は $D\cup A$ に属し、$C$ の頂点は $D$ と隣接しない。よって $G-A$ は $G[D]$ と $G[C]$ の交わりのない和で、その間に辺はない。とくに $\mathcal{K}$ の各成分は $G-A$ の成分であり、$G-A$ の最大マッチングは各成分の最大マッチングの和である。cor-ge-remove により $D(G-A)=D$、$C(G-A)=C$ である。
段 2（1 と 2）：$K\in\mathcal{K}$、$v\in V(K)$ とする。$v\in D(G-A)$ なので $v$ を飽和しない $G-A$ の最大マッチングがあり、その $K$ への制限は $v$ を飽和しない $K$ の最大マッチングである。よって $D(K)=V(K)$ であり、$K$ は連結なので lem-ge-gallai により因子臨界である。次に $G[C]$ の最大マッチング $M_C$ がある頂点 $c\in C$ を飽和しないとすると、$M_C$ と各 $K\in\mathcal{K}$ の最大マッチングの和は $c$ を飽和しない $G-A$ の最大マッチングになり、$c\in D(G-A)=D$ となって矛盾する。よって $M_C$ は $G[C]$ の完全マッチングである。
段 3（5）：段 2 から $\nu(K)=(|V(K)|-1)/2$ である。段 1 と cor-ge-remove により
$$ \nu(G)=\nu(G-A)+|A|=\sum_{K\in\mathcal{K}}\frac{|V(K)|-1}{2}+\frac{|C|}{2}+|A|=\frac{|D|-|\mathcal{K}|+|C|}{2}+|A|=\frac{|V|-|\mathcal{K}|+|A|}{2} $$
である。
段 4（4）：$M$ を最大マッチングとする。段 3 により、$M$ で飽和されない頂点はちょうど $|V|-2\nu(G)=|\mathcal{K}|-|A|$ 個である。$K\in\mathcal{K}$ の頂点数は奇数なので、$K$ の頂点のうち $K$ の内部の $M$ の辺で飽和されないものが少なくとも 1 つあり、それは $M$ で飽和されないか、$K$ の外の頂点と組む。$K$ の外の隣接頂点は $A$ に属する。$A$ の頂点と組む頂点をもつ成分の個数を $k$ とすると、$A$ の各頂点の相手は高々 1 つなので $k\le|A|$ であり、残りの $|\mathcal{K}|-k$ 個の成分はそれぞれ $M$ で飽和されない頂点を含む。よって
$$ |\mathcal{K}|-|A|\ \ge\ |\mathcal{K}|-k\ \ge\ |\mathcal{K}|-|A| $$
であり、等号が成り立つ。$k=|A|$ から、$A$ のすべての頂点が $D$ の頂点と組み、その相手は相異なる成分にある。前の不等式の等号から、$A$ と組む頂点をもたない成分はそれぞれ $M$ で飽和されない頂点をちょうど 1 つ含み、それ以外に $M$ で飽和されない頂点はない。したがって各 $K$ で、$K$ の内部の辺で飽和されない頂点はちょうど 1 つで、$M\cap E(K)$ はほぼ完全マッチングである。$C$ の頂点はすべて飽和され、その相手は $A$（$A$ の相手は $D$ にある）にも $D$（$D$ と $C$ の間に辺はない）にもないので $C$ にある。よって $M\cap E(G[C])$ は完全マッチングである。
段 5（3）：$X\subset A$ を空でないとし、$X$ の頂点と隣接する成分の集合を $\mathcal{K}_X$ とする。最大マッチングを 1 つとると、4 により $X$ の頂点は $\mathcal{K}_X$ の相異なる成分の頂点と組むので $|\mathcal{K}_X|\ge|X|$ である。$|\mathcal{K}_X|=|X|$ と仮定し、$K\in\mathcal{K}_X$ と $v\in V(K)$ をとる。$v\in D$ なので $v$ を飽和しない最大マッチング $M_v$ がある。4 により、$K$ の内部の辺で飽和されない $K$ の頂点は $v$ だけなので、$K$ には $A$ と組む頂点がない。すると $X$ の頂点は $\mathcal{K}_X\setminus\{K\}$ の相異なる成分の頂点と組むことになり、$|X|\le|X|-1$ となって矛盾する。$\square$

$\le$：$M$ をマッチング、$S\subset V$ とする。$G-S$ の頂点数が奇数の各成分は、その内部の $M$ の辺だけでは覆えないので、$M$ で飽和されない頂点か、$M$ で $S$ の頂点と組む頂点を含む。後者の成分は $|S|$ 個以下なので、$M$ で飽和されない頂点は $o(G-S)-|S|$ 個以上あり、$|V|-2|M|\ge o(G-S)-|S|$ である。
等号：$S=A:=A(G)$ とする。段 1 により $G-A$ の成分は、$\mathcal{K}$ の成分と $G[C]$ の成分である。前者は因子臨界なので頂点数が奇数である。$G[C]$ の完全マッチングは $G[C]$ の各成分の完全マッチングに分かれるので、後者の頂点数は偶数である。よって $o(G-A)=|\mathcal{K}|$ であり、thm-ge-main の 5 により $(|V|+|A|-o(G-A))/2=\nu(G)$ である。$\square$