タットの定理
P を、頂点 c から始まり、まず M1 に属す辺、次は M2 に属す辺、と交互にたどっていく G の極大経路(この条件を守りながらではそれよりも延ばすことができない経路)とする。この経路の終端の状況について考察する。
経路 P は、「特別」な頂点である x, a, b のいずれかに到達しない限り、必ずそれより長く延ばすことができる。なぜなら、頂点 c がマッチング M2 では辺 ca により接続されていることから、 P の最初の辺は M2 に属さない。よって c の次の頂点はマッチング M2 では c とは異なる頂点と接続されている。この辺はマッチング M1 には属さないから、第3の頂点は c とも第2の頂点とも異なる。以下、特別な頂点に到達しない限り全く同様の延長を繰り返すことができる。
v を経路 P の最後の頂点とする。もし経路 P の最後の辺が M1 に属しているとすると、v は a でなくてはいけない。なぜなら、さもなければ M2 から辺を選んで経路を延長できるからである(それにより x または b に達するかもしれない)。この場合、C : = P + ac と定義する。
もし経路 P の最後の辺が M2 に属しているとすると、この辺は ca と隣接していないから、v ∈ {x, b} でなければならない。この場合、 C : = P + va + ac と定義する。
このとき C は G + ac の偶数長の閉路で、M2 の元が1本おきに現れる辺集合となっている。よって M : = M2 Δ C (Δ は対称差)と定義したものは G の完全マッチングになる。これは G は完全マッチングを持たないとしていた仮定に反する。
なぜなら、グラフ G の悪い頂点部分集合 S は、G の任意の全域部分グラフ(spanning subgraph, 部分グラフであって元のグラフと頂点集合が一致するもの)の悪い頂点部分集合でもあるからである(奇頂点連結成分から辺を取り去ることでいくつかの連結成分に分裂したとすると、そのうち少なくとも1つの連結成分は頂点が奇数個でなければならない)。
S を、次数が |V| − 1 である頂点の集合(自分自身以外の全ての頂点と接続されているような頂点全体)と定義する。これが悪い頂点部分集合になることを以下場合分けして証明する。
G − S の全ての連結成分が完全グラフになる場合、S は悪い頂点部分集合である。なぜならもし o(G − S) ≤ |S| だとすると、各奇頂点連結成分と S の頂点とを結ぶ辺の集合と、それ以外の全ての頂点を余さず二人一組にするような辺集合の和集合が完全マッチングになるからである。
そうでない場合は、実はあり得ない。そのことを背理法で示す。
G − S のある連結成分 K が完全グラフではないとする。このとき xy ∉ E となる2頂点 x, y ∈ K が選べる。x, a, b ∈ K を、K 内で x, y を結ぶ最短経路の最初の3頂点だとする。すると xa, ab ∈ E かつ xb ∉ E である。a ∉ S だから、ac ∉ Eであるような頂点 c が存在する。G の辺極大性より G + xb の完全マッチング M1 、 G + ac の完全マッチング M2 がとれる。G 自身は完全マッチングを持たないと仮定しているのだから、xb ∈ M1 かつ ac ∈ M2 である。
グラフ G = (V, E) が完全マッチングを持つのは、頂点集合 V の任意の部分集合 U に対し、V − U から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数が高々 |U| 個であるとき、かつそのときに限る。