タットの定理
条件を以下のように書く。
( ∗ ) ∀ U ⊆ V , o ( V − U ) ≤ | U | {\displaystyle (*)\qquad \forall U\subseteq V,\quad o(V-U)\leq |U|}
ここで o ( X ) {\displaystyle o(X)} は X {\displaystyle X} から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数を表す。
(∗)の必要性: グラフ G に完全マッチングがあるとする。U を V の任意の部分集合として、グラフから U を除く。C を 誘導部分グラフ G − U の任意の奇頂点連結成分とする。G は完全マッチングを持つから、C にはそのマッチングにおいて U の要素と接続されていた頂点が少なくとも1つは存在する。
この対応付けによって G − U の奇頂点連結成分全体から U への写像が定まるが、これはマッチングの完全性より単射である。よって o(G − U) ≤ |U|。
(∗)の十分性: 完全マッチングを持たないグラフ G を任意にとる。このとき |S| < o(G − S) を満たす V の部分集合 S (以下これを「悪い」頂点部分集合と呼ぶ)が必ず存在する。ここで、
もし G の頂点数 |V| が奇数であるとすれば、G には少なくとも1個以上の奇頂点連結成分が存在するから、空集合 ∅ が悪い頂点部分集合になる。よって以下、頂点は偶数個であると仮定してよい。このとき o(G − U) と |U| の偶奇性は常に一致する。
さらに、G は辺極大(edge-maximal)である、つまり G に存在しないような任意の2頂点間の接続 e について、G + e が完全マッチングを持つようになると仮定してよい。