タットの定理

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

数学の分科、グラフ理論におけるタットの定理（タットのていり、テンプレート:Lang-en-short）とは、完全マッチングを持つグラフの特徴付けを与える定理である。名称はテンプレート:仮リンクにちなむ。この定理はホールの定理を2部グラフから任意のグラフへと一般化したものであり、またテンプレート:仮リンクの特殊な場合である。

定理

グラフ テンプレート:Math が完全マッチングを持つのは、頂点集合 テンプレート:Math の任意の部分集合 テンプレート:Math に対し、テンプレート:Math から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数が高々 テンプレート:Math 個であるとき、かつそのときに限る。

証明

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

$(*)\mathrm{\forall }U\subseteq V,o(V-U)\le |U|$

ここで $o(X)$ は $X$ から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数を表す。

(∗)の必要性： グラフ テンプレート:Math に完全マッチングがあるとする。テンプレート:Math を テンプレート:Math の任意の部分集合として、グラフから テンプレート:Math を除く。テンプレート:Math を 誘導部分グラフ テンプレート:Math の任意の奇頂点連結成分とする。テンプレート:Math は完全マッチングを持つから、テンプレート:Math にはそのマッチングにおいて テンプレート:Math の要素と接続されていた頂点が少なくとも1つは存在する。

この対応付けによって テンプレート:Math の奇頂点連結成分全体から テンプレート:Math への写像が定まるが、これはマッチングの完全性より単射である。よって テンプレート:Math。

(∗)の十分性： 完全マッチングを持たないグラフ テンプレート:Math を任意にとる。このとき テンプレート:Math を満たす テンプレート:Math の部分集合 テンプレート:Math （以下これを「悪い」頂点部分集合と呼ぶ）が必ず存在する。ここで、

• もし テンプレート:Math の頂点数 テンプレート:Math が奇数であるとすれば、テンプレート:Math には少なくとも1個以上の奇頂点連結成分が存在するから、空集合 テンプレート:Math が悪い頂点部分集合になる。よって以下、頂点は偶数個であると仮定してよい。このとき テンプレート:Math と テンプレート:Math の偶奇性は常に一致する。
• さらに、テンプレート:Math は辺極大（edge-maximal）である、つまり テンプレート:Math に存在しないような任意の2頂点間の接続 テンプレート:Math について、テンプレート:Math が完全マッチングを持つようになると仮定してよい。

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

テンプレート:Math を、次数が テンプレート:Math である頂点の集合（自分自身以外の全ての頂点と接続されているような頂点全体）と定義する。これが悪い頂点部分集合になることを以下場合分けして証明する。

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

元のグラフ テンプレート:Math の辺であるものを実線で示す。テンプレート:Math と テンプレート:Math は同一の頂点かもしれない。

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

テンプレート:Math のある連結成分 テンプレート:Math が完全グラフではないとする。このとき テンプレート:Math となる2頂点 テンプレート:Math が選べる。テンプレート:Math を、テンプレート:Math 内で テンプレート:Math を結ぶ最短経路の最初の3頂点だとする。すると テンプレート:Math かつ テンプレート:Math である。テンプレート:Math だから、テンプレート:Mathであるような頂点 テンプレート:Math が存在する。テンプレート:Math の辺極大性より テンプレート:Math の完全マッチング テンプレート:Math 、 テンプレート:Math の完全マッチング テンプレート:Math がとれる。テンプレート:Math 自身は完全マッチングを持たないと仮定しているのだから、テンプレート:Math かつ テンプレート:Math である。

テンプレート:Math を、頂点 テンプレート:Math から始まり、まず テンプレート:Math に属す辺、次は テンプレート:Math に属す辺、と交互にたどっていく テンプレート:Math の極大経路（この条件を守りながらではそれよりも延ばすことができない経路）とする。この経路の終端の状況について考察する。

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

テンプレート:Math を経路 テンプレート:Math の最後の頂点とする。もし経路 テンプレート:Math の最後の辺が テンプレート:Math に属しているとすると、テンプレート:Math は テンプレート:Math でなくてはいけない。なぜなら、さもなければ テンプレート:Math から辺を選んで経路を延長できるからである（それにより テンプレート:Math または テンプレート:Math に達するかもしれない）。この場合、テンプレート:Math と定義する。

もし経路 テンプレート:Math の最後の辺が テンプレート:Math に属しているとすると、この辺は テンプレート:Math と隣接していないから、テンプレート:Math でなければならない。この場合、 テンプレート:Math と定義する。

このとき テンプレート:Math は テンプレート:Math の偶数長の閉路で、テンプレート:Math の元が1本おきに現れる辺集合となっている。よって テンプレート:Math （テンプレート:Math は対称差）と定義したものは テンプレート:Math の完全マッチングになる。これは テンプレート:Math は完全マッチングを持たないとしていた仮定に反する。

関連項目

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

参考文献

• テンプレート:Cite book
• テンプレート:Cite book