因子臨界グラフ

1：頂点 $v$ をとると、$G-v$ の完全マッチングは $|V|-1$ 個の頂点を 2 個ずつ組にするので、$|V|-1$ は偶数である。完全マッチングをもつグラフの頂点数は偶数なので、$G$ は完全マッチングをもたない。
2：$G$ が 2 つ以上の連結成分(グラフ)をもつとし、成分 $K$ を 1 つとる。$K$ の外の頂点 $v$ をとると、$K$ は $G-v$ の成分でもあり、$G-v$ の完全マッチングの辺は成分の中にあるので、$K$ の頂点数は偶数である。どの成分 $K$ にも外の頂点があるので、すべての成分の頂点数が偶数となり、$|V|$ が奇数であることに反する。
3：次数 $0$ の頂点は、2 により $|V|=1$ のときしかない。次数 $1$ の頂点 $x$ があり、その唯一の隣接頂点を $y$ とする。$G-y$ では $x$ は孤立点なので、$G-y$ の完全マッチングは $x$ を飽和できず矛盾する。$\square$

頂点 $v$ を固定する。$(G-v)-T=G-(T\cup\{v\})$ なので、Tutteの定理 の主定理「Tutte の定理」を $G-v$ に当てると、$G-v$ が完全マッチングをもつことは、すべての $T\subset V\setminus\{v\}$ について $o\bigl(G-(T\cup\{v\})\bigr)\le|T|$ であることと同値である。$S:=T\cup\{v\}$ とおけば $|T|=|S|-1$ であり、$T$ が $V\setminus\{v\}$ の部分集合を動くとき $S$ は $v$ を含む $V$ の部分集合をちょうど 1 回ずつ動く。よって $G-v$ が完全マッチングをもつことは、$v$ を含むすべての $S\subset V$ について $o(G-S)\le|S|-1$ であることと同値である。これをすべての $v$ についてあわせると、空でないすべての $S$ についての条件 2 になる。$\square$

1 ⇒ 2：$|V|=2k+1$ とすると（prop-fc-basic の 1）、どのマッチングも偶数個の頂点しか飽和しないので $\nu(G)\le k$ であり、$G-v$ の完全マッチングは大きさ $k$ で $v$ を飽和しない最大マッチングである。連結性は prop-fc-basic の 2 による。
2 ⇒ 1 は Gallai の補題であり、この記事では証明しない（証明は Gallai–Edmondsの分解定理 の補題「Gallai の補題」）。$\square$

1：長さ $\ell$ の耳は、開いていても閉じていても、$\ell$ 本の辺と $\ell-1$ 個の内部の頂点を加える。よって 1 つの耳ごとに「辺の本数 $-$ 頂点の個数」はちょうど $1$ 増える。$G_0$ では $0-1=-1$ なので、$G_r=G$ では $|E|-|V|=-1+r$ である。
2：$i$ についての帰納法で、$G_i$ が連結で、$G_i$ のどの辺も $G_i$ の閉路の上にあることを示す（$i=0$ では辺がない）。閉じた耳 $P_i$ は $G_{i-1}$ の頂点 1 個を含む閉路なので、$G_i$ は連結で、$P_i$ の辺は $P_i$ の上にある。開いた耳 $P_i$ の端点を $a\ne b$ とすると、$G_{i-1}$ は連結なので $G_{i-1}$ に $a$ から $b$ への道 $Q$ がある。$Q$ の辺は $G_{i-1}$ の辺で $P_i$ の辺は $G_{i-1}$ の辺でなく、$Q$ と $P_i$ の共有点は $a,b$ だけなので、$Q$ と $P_i$ をつないだものは閉路である。$\square$

$P=x_0x_1\cdots x_\ell$、$\ell=2s+1$ とする（閉じた耳なら $x_\ell=x_0$）。内部の頂点は $x_1,\dots,x_{2s}$ の $2s$ 個である。$H\cup P$ の頂点 $z$ をとり、$z$ だけを飽和しないほぼ完全マッチングを作る。

• $z\in V(H)$ のとき：$H-z$ の完全マッチングに、$x_1x_2,\ x_3x_4,\ \dots,\ x_{2s-1}x_{2s}$ を加える。
• $z=x_i$ で $i$ が奇数のとき：$x_1x_2,\dots,x_{i-2}x_{i-1}$ と $x_{i+1}x_{i+2},\dots,x_{2s}x_{2s+1}$（$x_1,\dots,x_{i-1}$ は $i-1$ 個、$x_{i+1},\dots,x_{2s+1}$ は $2s+1-i$ 個で、どちらも偶数個）に、$H-x_\ell$ の完全マッチングを加える。
• $z=x_i$ で $i$ が偶数のとき：$x_0x_1,\dots,x_{i-2}x_{i-1}$ と $x_{i+1}x_{i+2},\dots,x_{2s-1}x_{2s}$（$x_0,\dots,x_{i-1}$ は $i$ 個、$x_{i+1},\dots,x_{2s}$ は $2s-i$ 個）に、$H-x_0$ の完全マッチングを加える。
  どの場合も、加えた $P$ の辺は $H$ の頂点を高々 1 つ（$x_0$ か $x_\ell$）しか使わず、その頂点は $H$ のマッチングで飽和されない頂点なので、全体はマッチングであり、$z$ 以外のすべての頂点を飽和する。$\square$

2 ⇒ 1：奇耳分解 $G_0\subset\cdots\subset G_r=G$ をとる。$G_0=K_1$ は因子臨界であり、lem-fc-add-ear により $G_{i-1}$ が因子臨界なら $G_i$ も因子臨界である。
1 ⇒ 2：頂点 $v$ を固定し、$G-v$ の完全マッチング $M$ をとる。$M$ は $v$ だけを飽和しない。$G$ の部分グラフ $H$ で、次の 2 条件を満たすものを考える。
(a) $H$ は $v$ だけからなる $H_0$ から始まる奇耳分解をもつ。
(b) $M$ の辺で、一方の端点だけが $V(H)$ に属するものはない。
$H=H_0$ は (a)(b) を満たす（$v$ は $M$ で飽和されない）。(a)(b) を満たす $H$ で $V(H)\ne V$ のものから、(a)(b) を満たし頂点が真に多い $H'$ を作る。
$G$ は連結（prop-fc-basic の 2）なので、$V(H)$ に属さない頂点 $y$ で、$V(H)$ のある頂点 $h$ と隣接するものがある。$G-y$ の完全マッチング $N$ をとり、頂点集合 $V$、辺集合 $M\triangle N$（対称差）のグラフを考える。各頂点には $M$ の辺と $N$ の辺が高々 1 本ずつ接続するので、このグラフの次数は $2$ 以下である。$v$ は $N$ だけで飽和されるので次数 $1$、$y$ は $M$ だけで飽和されるので次数 $1$、ほかの頂点は $M$ と $N$ の両方で飽和されるので次数 $0$ か $2$ である。よって $v$ を含む成分は道で、もう一方の端点は次数 $1$ の頂点 $y$ である。この道を
$$ v=q_0,\ q_1,\ \dots,\ q_t=y $$
とする。$v$ での辺は $N$ に属し、辺は $N$ と $M$ に交互に属するので、$q_kq_{k+1}$ は $k$ が偶数なら $N\setminus M$、奇数なら $M\setminus N$ に属する。$y$ での最後の辺は $M$ に属するので、$t$ は偶数である。
$q_j\notin V(H)$ となる最小の $j$ をとる（$q_t=y$ なのでとれ、$j\ge1$）。辺 $q_{j-1}q_j$ は $V(H)$ とその外を結ぶので (b) により $M$ に属さず、$j-1$ は偶数、すなわち $j$ は奇数である。$t$ は偶数なので $j< t$ であり、$q_jq_{j+1}\in M$ である。(b) により、$M$ で $V(H)$ の外の頂点と組む頂点は $V(H)$ の外にあるので、$q_{j+1}\notin V(H)$ である。

• 道が $V(H)$ に戻るとき：$l>j$ で $q_l\in V(H)$ となる最小の $l$ をとる。辺 $q_{l-1}q_l$ は (b) により $M$ に属さないので $l-1$ は偶数、$l$ は奇数であり、$q_{j+1}\notin V(H)$ から $l\ge j+2$ である。$P:=q_{j-1}q_j\cdots q_l$ は、相異なる端点 $q_{j-1},q_l$ が $V(H)$ に属し、内部の頂点 $q_j,\dots,q_{l-1}$ が $V(H)$ に属さない道で、長さ $l-j+1$ は $3$ 以上の奇数である。
• 道が $V(H)$ に戻らないとき：$q_j,\dots,q_t$ はどれも $V(H)$ に属さない。$P:=q_{j-1}q_j\cdots q_t h$ とおく。$h\in V(H)$ は $q_j,\dots,q_t$ のどれとも異なり、長さ $t-j+2$ は $3$ 以上の奇数である。$h\ne q_{j-1}$ なら $P$ は開いた耳、$h=q_{j-1}$ なら閉じた耳である。
  どちらの場合も $P$ は $H$ の長さが奇数の耳で、内部の頂点は $q_j,q_{j+1},\dots,q_{j'}$（$j$ は奇数、$j'$ は偶数）と並ぶ。辺 $q_jq_{j+1},q_{j+2}q_{j+3},\dots,q_{j'-1}q_{j'}$ は $M$ に属するので、内部の頂点は $M$ で内部の頂点どうしと組む。よって $H':=H\cup P$ は (a)(b) を満たし、$H$ より頂点が多い。
  これを繰り返すと、(a)(b) を満たし $V(H)=V$ である $H$ が得られる。$G$ の辺で $H$ の辺でないものは両端が $V(H)$ に属するので、長さ $1$ の開いた耳として 1 本ずつ加えられる。こうして $G$ の奇耳分解で、$G_0$ が $v$ だけからなるものが得られる。$\square$

thm-fc-lovasz により奇耳分解があるので、lem-fc-ear-count の 2 による。閉路の上の辺を除いても、その閉路の残りの道で両端が結ばれるので連結性は保たれる。$\square$

$G$ の頂点 $z$ をとる。$z\in V(H)$ のとき：$G/H-h=G-V(H)$ の完全マッチングに $H-z$ の完全マッチングを加えると、$G-z$ の完全マッチングになる。$z\notin V(H)$ のとき：$G/H-z$ の完全マッチング $N$ で $h$ と組む頂点を $y$ とし、$y$ と $G$ で隣接する $x\in V(H)$ をとる。$N$ の辺 $hy$ を $G$ の辺 $xy$ に置き換え、$H-x$ の完全マッチングを加えると、$G-z$ の完全マッチングになる。$\square$