タットの定理

数学の分科、グラフ理論におけるタットの定理（タットのていり、）とは、完全マッチングを持つグラフの特徴付けを与える定理である。名称はにちなむ。この定理はホールの定理を2部グラフから任意のグラフへと一般化したものであり、またの特殊な場合である。
定理.
グラフ が完全マッチングを持つのは、頂点集合 の任意の部分集合 に対し、 から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数が高々 個であるとき、かつそのときに限る。
証明.
条件を以下のように書く。
ここで formula_2 は formula_3 から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数を表す。
(∗)の必要性： グラフ に完全マッチングがあるとする。 を の任意の部分集合として、グラフから を除く。 を 誘導部分グラフ の任意の奇頂点連結成分とする。 は完全マッチングを持つから、 にはそのマッチングにおいて の要素と接続されていた頂点が少なくとも1つは存在する。
この対応付けによって の奇頂点連結成分全体から への写像が定まるが、これはマッチングの完全性より単射である。よって 。
(∗)の十分性： 完全マッチングを持たないグラフ を任意にとる。このとき を満たす の部分集合 （以下これを「悪い」頂点部分集合と呼ぶ）が必ず存在する。ここで、
 を、次数が である頂点の集合（自分自身以外の全ての頂点と接続されているような頂点全体）と定義する。これが悪い頂点部分集合になることを以下場合分けして証明する。