タットの定理

中央の頂点を除くと、頂点数がいずれも5の3個の連結成分が生じる。よってタットの定理より、このグラフは完全マッチングを持たない。

数学の分科、グラフ理論におけるタットの定理（タットのていり、英: Tutte theorem）とは、完全マッチングを持つグラフの特徴付けを与える定理である。名称はウィリアム・トーマス・タットにちなむ。この定理はホールの定理を2部グラフから任意のグラフへと一般化したものであり、またタット-ベルジュの公式の特殊な場合である。

定理

グラフ G = (V, E) が完全マッチングを持つのは、頂点集合 V の任意の部分集合 U に対し、V − U から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数が高々 |U| 個であるとき、かつそのときに限る。

証明

条件を以下のように書く。

$(*)\qquad \forall U\subseteq V,\quad o(V-U)\leq |U|$

ここで $o(X)$ は $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 が完全マッチングを持つようになると仮定してよい。

なぜなら、グラフ G の悪い頂点部分集合 S は、G の任意の全域部分グラフ（spanning subgraph, 部分グラフであって元のグラフと頂点集合が一致するもの）の悪い頂点部分集合でもあるからである（奇頂点連結成分から辺を取り去ることでいくつかの連結成分に分裂したとすると、そのうち少なくとも1つの連結成分は頂点が奇数個でなければならない）。

S を、次数が |V| − 1 である頂点の集合（自分自身以外の全ての頂点と接続されているような頂点全体）と定義する。これが悪い頂点部分集合になることを以下場合分けして証明する。

• G − S の全ての連結成分が完全グラフになる場合、S は悪い頂点部分集合である。なぜならもし o(G − S) ≤ |S| だとすると、各奇頂点連結成分と S の頂点とを結ぶ辺の集合と、それ以外の全ての頂点を余さず二人一組にするような辺集合の和集合が完全マッチングになるからである。

元のグラフ G = (V, E) の辺であるものを実線で示す。b と y は同一の頂点かもしれない。

• そうでない場合は、実はあり得ない。そのことを背理法で示す。

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 の完全マッチング M₁ 、 G + ac の完全マッチング M₂ がとれる。G 自身は完全マッチングを持たないと仮定しているのだから、xb ∈ M₁ かつ ac ∈ M₂ である。

P を、頂点 c から始まり、まず M₁ に属す辺、次は M₂ に属す辺、と交互にたどっていく G の極大経路（この条件を守りながらではそれよりも延ばすことができない経路）とする。この経路の終端の状況について考察する。

経路 P は、「特別」な頂点である x, a, b のいずれかに到達しない限り、必ずそれより長く延ばすことができる。なぜなら、頂点 c がマッチング M₂ では辺 ca により接続されていることから、 P の最初の辺は M₂ に属さない。よって c の次の頂点はマッチング M₂ では c とは異なる頂点と接続されている。この辺はマッチング M₁ には属さないから、第3の頂点は c とも第2の頂点とも異なる。以下、特別な頂点に到達しない限り全く同様の延長を繰り返すことができる。

v を経路 P の最後の頂点とする。もし経路 P の最後の辺が M₁ に属しているとすると、v は a でなくてはいけない。なぜなら、さもなければ M₂ から辺を選んで経路を延長できるからである（それにより x または b に達するかもしれない）。この場合、C : = P + ac と定義する。

もし経路 P の最後の辺が M₂ に属しているとすると、この辺は ca と隣接していないから、v ∈ {x, b}  でなければならない。この場合、 C : = P + va + ac と定義する。

このとき C は G + ac の偶数長の閉路で、M₂ の元が1本おきに現れる辺集合となっている。よって M : = M₂ Δ C （Δ は対称差）と定義したものは G の完全マッチングになる。これは G は完全マッチングを持たないとしていた仮定に反する。

関連項目

• ホールの定理
• ピーターセンの定理

参考文献

• Bondy, J. A.; Murty, U. S. R. (1976). Graph theory with applications. New York: American Elsevier Pub. Co.. ISBN 0-444-19451-7 
• Lovász, László; Plummer, M. D. (1986). Matching theory. Amsterdam: North-Holland. ISBN 0-444-87916-1