Tutteの定理

$G-S$ は $G'-S$ の全域部分グラフなので、$G-S$ の各成分の頂点は $G'-S$ の 1 つの成分に含まれる。したがって $G'-S$ の各成分 $K$ の頂点集合は、$G-S$ のいくつかの成分の頂点集合の交わらない和集合である。$K$ が奇成分なら、その頂点数は奇数であり、偶数の和は偶数だから、$K$ に含まれる $G-S$ の成分のうち少なくとも 1 つは奇成分である。$G'-S$ の各奇成分にそこに含まれる $G-S$ の奇成分を 1 つ選べば、$G'-S$ の相異なる成分は頂点を共有しないので、選ばれる奇成分も相異なる。よって $o(G'-S)\le o(G-S)$ である。$\square$

必要性を示したあと、十分性を 3 段で示す。辺について極大な反例に取り替え（段 1、lem-tutte-supergraph を使う）、その形を調べ（段 2）、完全マッチングを組み立てて矛盾を導く（段 3）。
必要性：$M$ を $G$ の完全マッチングとし、$S\subset V$ とする。$C$ を $G-S$ の奇成分とする。$C$ の頂点数は奇数なので、$C$ の頂点を $C$ の中の $M$ の辺だけで覆うことはできず、$M$ で $C$ の外の頂点と組む頂点 $c\in C$ がある。$C$ は $G-S$ の成分なので、$c$ の隣接頂点のうち $C$ の外にあるものは $S$ に属する。そこで $c$ の相手を $s_C\in S$ とおく。$M$ はマッチングなので、相異なる奇成分 $C\neq C'$ について $s_C\neq s_{C'}$ である。$C\mapsto s_C$ は奇成分の集合から $S$ への 単射 であり、$o(G-S)\le|S|$ を得る。
十分性：$G$ が Tutte の条件を満たすが完全マッチングをもたないと仮定して矛盾を導く。
段 1（辺について極大なグラフに取り替える）：頂点集合 $V$ 上のグラフで、$G$ の辺をすべて含み、完全マッチングをもたないものの全体は、$G$ 自身を含むので空でなく、有限個である。そのうち辺の本数が最大のものを $G^*=(V,E^*)$ とする。lem-tutte-supergraph により $G^*$ も Tutte の条件を満たし、とくに $|V|$ は偶数である。$G^*$ は完全マッチングをもたないが、$E^*$ に属さない辺 $e$ を 1 本加えた $G^*+e$ は、辺の本数の最大性により完全マッチングをもつ。
段 2（全体と隣接する頂点の集合 $U$）：$G^*$ の頂点のうち、他のすべての頂点と隣接するものの集合を $U$ とする。$G^*-U$ の各成分が 完全グラフ であることを示す。そうでないとして、$G^*-U$ の成分 $K$ に隣接しない 2 頂点があるとする。$K$ の中でそれらを結ぶ最短の道をとり、その最初の 3 頂点を $a,b,c$ とすると、$ab,bc\in E^*$、$ac\notin E^*$ である（$ac\in E^*$ なら道を短くできる）。$b\notin U$ なので、$b$ と隣接しない頂点 $d\neq b$ がある。$ab,bc\in E^*$ だから $d\neq a,c$ である。段 1 により、$G^*+ac$ は完全マッチング $M_1$ を、$G^*+bd$ は完全マッチング $M_2$ をもつ。$G^*$ には完全マッチングがないので $ac\in M_1$、$bd\in M_2$ であり、$\{a,c\}\neq\{b,d\}$ だから $ac\notin M_2$、$bd\notin M_1$ である。
対称差 $M_1\triangle M_2$（対称差）を辺集合とするグラフ $H$ を考える。各頂点には $M_1$ の辺と $M_2$ の辺がちょうど 1 本ずつ接続するので、$H$ での次数は $0$ か $2$ で、次数 $2$ の頂点では $M_1\setminus M_2$ の辺と $M_2\setminus M_1$ の辺が 1 本ずつ接続する。よって $H$ の辺は、$M_1$ と $M_2$ の辺が交互に並ぶ互いに交わらない閉路に分かれる。辺 $ac$ と $bd$ はともに $H$ に属する。$bd$ を含む閉路を $C$ とする。

• $ac$ が $C$ に含まれないとき：$C$ の上の $M_1$ の辺と、$C$ の外の $M_2$ の辺を合わせた集合 $M$ を考える。$C$ の頂点は $C$ の上の $M_1$ の辺でちょうど 1 回ずつ覆われ、$C$ の外の頂点はその $M_2$ の辺（$C$ の上にはない）でちょうど 1 回ずつ覆われる。$C$ の上の $M_1$ の辺は $ac$ でなく、$C$ の外の $M_2$ の辺は $bd$ でないので、$M\subset E^*$ である。$M$ は $G^*$ の完全マッチングとなり、矛盾する。
• $ac$ が $C$ に含まれるとき：$C$ を $b$ から辺 $bd$ の向きにたどり、$a$ と $c$ のうち先に現れる方を $y$ とする。$d$ から $y$ までの $C$ の部分の道を $Q$ とする。$Q$ は $b$ を通らず、$a,c$ のうち $y$ しか含まないので辺 $ac$ を含まない。$Q$ は $d$ の $M_1$ の辺から始まり（$d$ の $M_2$ の辺は $bd$ である）、$y$ の $M_2$ の辺で終わる（$y$ の $M_1$ の辺は $ac$ である）。$y\in\{a,c\}$ は $b$ と隣接するので、$Q$ に辺 $yb$ と $bd$ を加えると閉路 $C'$ ができる。そこで
  $$ M:=\bigl(M_2\setminus E(C')\bigr)\cup\bigl(M_1\cap E(Q)\bigr)\cup\{yb\} $$
  とおく。$C'$ の頂点に接続する $M_2$ の辺はすべて $C'$ の上にあるので第 1 の集合からは除かれ、$d$ と $Q$ の内部の頂点は $Q$ の上の $M_1$ の辺で、$y$ と $b$ は $yb$ でちょうど 1 回ずつ覆われる。$C'$ の外の頂点は $M_2$ の辺でちょうど 1 回ずつ覆われる。$bd\notin M$、$ac\notin M$ だから $M\subset E^*$ であり、$M$ は $G^*$ の完全マッチングとなって矛盾する。
  どちらの場合も矛盾なので、$G^*-U$ の各成分は完全グラフである。

段 3（完全マッチングを組み立てる）：Tutte の条件を $S=U$ に使うと $o(G^*-U)\le|U|$ である。$G^*-U$ の各奇成分 $K$ から頂点 $k_K$ を 1 つ選び、相異なる $u_K\in U$ と組ませる（$U$ の頂点は他のすべての頂点と隣接する）。各奇成分の残りの頂点は偶数個で、成分は完全グラフなので 2 つずつ組める。偶成分も同様に組める。ここまでに組んだ頂点の個数は偶数で、$|V|$ も偶数なので、残る $U$ の頂点も偶数個であり、互いに隣接するので 2 つずつ組める。これは $G^*$ の完全マッチングであり、段 1 の仮定に反する。$\square$

$G=(V,E)$ を橋をもたない 3-正則グラフとし、Tutte の条件を確かめる。$S\subset V$ とし、$C$ を $G-S$ の奇成分とする。$C$ と $V\setminus C$ を結ぶ辺の本数を $m_C$ とする。$C$ は $G-S$ の成分なので、これらの辺の $C$ の外の端点はすべて $S$ に属する。$C$ の頂点の次数の和は、$C$ の内部の辺の本数を $e_C$ として
$$ 3|C|=2e_C+m_C $$
であり、$|C|$ は奇数なので $m_C$ は奇数である。とくに $m_C\ge1$ である。$m_C=1$ とすると、その 1 本の辺 $e$ を除いたグラフでは $C$ と $V\setminus C$ を結ぶ辺がなくなる。$G$ では $e$ の両端点は同じ成分にあるが、$G-e$ では $C$ の頂点と $e$ の $S$ 側の端点は別の成分に入るので、成分の個数が増え、$e$ は橋になる。これは仮定に反するので $m_C\ge3$ である。
$S$ の頂点に接続する辺は高々 $3|S|$ 本なので、奇成分について和をとると
$$ 3\,o(G-S)\le\sum_{C}m_C\le3|S| $$
であり（左の和は $G-S$ の奇成分 $C$ 全体にわたる。相異なる奇成分から $S$ へ出る辺は相異なる）、$o(G-S)\le|S|$ を得る。thm-tutte-main により $G$ は完全マッチングをもつ。$\square$

$\le$：$M$ を任意のマッチング、$S\subset V$ とする。$G-S$ の各奇成分 $C$ は、$M$ の $C$ の内部の辺だけでは覆えないので、$M$ で飽和されない頂点を含むか、$M$ で $S$ の頂点と組む頂点を含む。後者の奇成分は、prf-tutte-main の必要性と同じ理由で $|S|$ 個以下である。よって $M$ で飽和されない頂点は $o(G-S)-|S|$ 個以上あり、$|V|-2|M|\ge o(G-S)-|S|$、すなわち $|M|\le(|V|+|S|-o(G-S))/2$ である。
$\ge$：$d:=\max_{S\subset V}(o(G-S)-|S|)$ とおく。$S=\emptyset$ で $o(G)\ge0$ なので $d\ge0$ である。$G-S$ の偶成分の頂点数は偶数なので $o(G-S)\equiv|V|-|S|\pmod 2$ であり、したがって $o(G-S)-|S|\equiv|V|\pmod2$、とくに $d\equiv|V|\pmod 2$ である。
$G$ に $d$ 個の新しい頂点の集合 $W$ を加え、$W$ の各頂点を $V\cup W$ の他のすべての頂点と辺で結んだグラフを $G'$ とする（グラフ の記事の定義「補グラフとグラフの和」の結合 $G+K_d$）。$G'$ が Tutte の条件を満たすことを示す。$S'\subset V\cup W$ とする。

• $W\not\subset S'$ のとき：$S'$ に入らない $W$ の頂点が残りのすべての頂点と隣接するので、$G'-S'$ は連結であり、$o(G'-S')\le1$ である。$S'=\emptyset$ なら、$G'$ の頂点数 $|V|+d$ は偶数なので $o(G')=0$ である。$S'\neq\emptyset$ なら $o(G'-S')\le1\le|S'|$ である。
• $W\subset S'$ のとき：$S:=S'\cap V$ とおくと $G'-S'=G-S$ であり、$o(G'-S')=o(G-S)\le|S|+d=|S'|$ である。
  thm-tutte-main により $G'$ は完全マッチング $M'$ をもつ。$W$ の頂点を端点にもつ $M'$ の辺は $d$ 本以下なので、それらを除いた $M:=M'\cap E$ は $G$ のマッチングで
  $$ |M|\ge\frac{|V|+d}{2}-d=\frac{|V|-d}{2} $$
  である。$d=o(G-S_0)-|S_0|$ となる $S_0$ をとれば、右辺は $(|V|+|S_0|-o(G-S_0))/2$ であり、これは最小値以上である。よって $\nu(G)$ は最小値以上であり、前半とあわせて最小値に等しい。$\square$