トゥッテ定理

数学のグラフ理論の分野において、ウィリアム・トーマス・タットにちなんで名付けられたタットの定理は、完全マッチングを持つ有限無向グラフの特徴付けであり、タット・ベルゲの公式の特殊なケースです。

目標は、完全マッチングを持たないすべてのグラフを特徴付けることです。完全マッチングを持たないグラフの最も明白なケース、つまり、頂点の数が奇数であるグラフから始めます。このようなグラフでは、マッチングを行うと少なくとも 1 つの一致しない頂点が残るため、完全ではありません。

もう少し一般的なケースは、1 つ以上のコンポーネントに奇数の頂点がある (頂点の総数が偶数であっても) 切断されたグラフです。このようなコンポーネントを奇数コンポーネントと呼びます。どのマッチングでも、各頂点は同じコンポーネントの頂点にのみ一致します。したがって、どのマッチングでも、奇数コンポーネントごとに少なくとも 1 つの一致しない頂点が残るため、マッチングは完全ではありません。

次に、頂点uを持つグラフGを考えます。Gから頂点uとその隣接する辺を削除すると、残りのグラフ ( G  −  uと表記) には2つ以上の奇数コンポーネントが含まれます。前述のように、マッチングでは、すべての奇数コンポーネントに、同じコンポーネント内の他の頂点と一致しない頂点が少なくとも 1 つ残ります。このような頂点はuとのみ一致できます。ただし、一致しない頂点が 2 つ以上あり、そのうち 1 つだけがuと一致するため、少なくとも他の 1 つの頂点は一致しないままになり、マッチングは完全ではありません。

最後に、頂点の集合Uを持つグラフGを考えます。G から U 内の頂点とそれらに隣接するすべての辺を削除すると、残りのグラフ ( G  −  Uと表記) には| U |個以上の奇数コンポーネントが含まれます。上で説明したように、どのマッチングでも、奇数コンポーネントごとに少なくとも 1 つの一致しない頂点が残り、これらはUの頂点にのみマッチングできますが、 Uにはこれらの一致しない頂点すべてに対応する頂点がないため、マッチングは完全ではありません。

必要条件に到達しました。Gが完全マッチングを持つ場合、G内のすべての頂点サブセットUに対して、グラフG  −  U には最大で| U | 個の奇数コンポーネントが含まれます。タットの定理によれば、この条件は完全マッチングの存在に必要かつ十分です。

グラフG  = ( V ,  E )が完全マッチング を持つのは、Vのすべての部分集合Uに対して、部分グラフG  −  Uが最大で| U |個の奇数個の成分（奇数の頂点を持つ連結成分）を持つ場合に限られます。^[1]

まず条件を記述します:

${\displaystyle (*)\qquad \forall U\subseteq V,\quad odd(GU)\leq |U|}$

ここで、 はによって誘導されるサブグラフの奇数成分の数を表します。 ${\displaystyle 奇数(X)}$${\displaystyle X}$

(∗) の必要性:この方向については、以下の「直観」のセクションですでに説明しましたが、ここで証明をまとめましょう。完全マッチングを持つグラフGを考えます。UをVの任意の部分集合とします。U を削除します。C をG  −  Uの任意の奇数成分とします。G は完全マッチングを持つため、 Cの少なくとも 1 つの頂点はUの頂点とマッチングする必要があります。したがって、各奇数成分には、 Uの頂点とマッチングする頂点が少なくとも 1 つあります。U の各頂点は、最大で 1 つの接続成分とこの関係を持つことができるため(完全マッチングで最大で 1 回マッチングされるため)、奇数( G  −  U ) ≤ | U |です。^[2]

(∗) の十分性: G を完全マッチングのない任意のグラフとします。いわゆる Tutte 違反者、つまり | S | < odd ( G − S ) となる V のサブセット S が見つかります。Gは辺最大 、つまりG  +  eはGにまだ存在しないすべての 辺 eに対して完全マッチングを持つと仮定できます。実際、辺最大グラフGでTutte 違反者Sが見つかった場合、SはGのすべてのスパニング サブグラフでも Tutte 違反者になります。これは、 G  −  Sのすべての奇数コンポーネントが、少なくとも 1 つが再び奇数になる可能性のあるより多くのコンポーネントに分割されるためです。

S を次数| V | − 1の頂点の集合として定義します。まず、 G  −  Sのすべてのコンポーネントが完全グラフである場合を考えます。すると、奇数( G  −  S ) ≤ | S |であれば、すべての奇数コンポーネントの 1 つの頂点をSの 1 つの頂点と一致させ、他のすべての頂点をペアにすることで完全なマッチングを見つけることができるため、Sは Tutte 違反になります ( | V |が奇数でない限りこれは機能しますが、その場合∅ はTutte 違反になります)。

ここで、K がG  −  Sの要素であり、x、  y  ∈  Kがxy  ∉  Eとなる頂点であるとします。x、  a、  b  ∈  K をKの最短x、yパス上の最初の頂点とします。これにより、 xa、  ab  ∈  Eおよびxb  ∉  Eが保証されます。a  ∉  Sなので、 ac  ∉  Eとなる頂点c が存在します。 Gの辺最大性から、 M _{1 を}G  +  xbにおける完全マッチングとして、M _{2 を}G  +  acにおける完全マッチングとして定義します。 xb  ∈  M ₁およびac  ∈  M ₂であることに注目してください。

P を、cから始まり、M ₁からの辺を持ち、辺がM ₁とM _{2の間で交互に存在する}G内の最大パスとします。P はどのように終了するのでしょうか? x、  a、bなどの「特別な」頂点に到達しない限り、常に続行できます。c はcaによってM ₂に一致するため、 Pの最初の辺はM ₂に含まれず、したがって 2 番目の頂点は別の辺によって M _{2に一致し、このように続行されます。}

v をPの最後の頂点とします。Pの最後の辺がM ₁にある場合、v はaでなければなりません。そうしないと、 M ₂からの辺が続く可能性があるためです( xまたはbに到達する場合も含む)。この場合、C := P  +  acと定義します。 Pの最後の辺がM ₂にある場合、同様の理由でv  ∈ { x ,  b } であることは確実であり、 C := P  +  va  +  acと定義します。

ここで、C はG  +  ac内の偶数長のサイクルであり、他のすべての辺はM _{2内にあります。ここで、} M := M ₂  Δ  C ( Δは対称差)と定義でき、 G内の完全マッチングが得られますが、これは矛盾です。

Tutte -Berge の公式によれば、グラフの最大マッチングのサイズは に等しいとされています。同様に、最大マッチングにおけるマッチングされていない頂点の数は に等しいです。 ${\displaystyle G=(V,E)}$${\displaystyle \min _{U\subseteq V}\left(|U|-\operatorname {odd} (GU)+|V|\right)/2}$${\displaystyle \max _{U\subseteq V}\left(\operatorname {odd} (GU)-|U|\right)}$

この式は、 の元の頂点すべてに新しい頂点をそれぞれ追加して得られるグラフが完全マッチングを持つ場合のみ、のサイズのマッチングを持つという観察とともに、タットの定理から導かれます。が 以上の要素に分離する集合は、必ずすべての新しい頂点を含まなければならないため、の場合にのみ、(*) が に対して満たされます。 ${\displaystyle G}$${\displaystyle k}$${\displaystyle G^{(k)}}$${\displaystyle |V|-2k}$${\displaystyle G}$${\displaystyle X}$${\displaystyle G^{(k)}}$${\displaystyle |X|}$${\displaystyle G^{(k)}}$${\displaystyle k\leq \min _{U\subseteq V}\left(|U|-\operatorname {odd} (GU)+|V|\right)/2}$

局所有限な連結無限グラフ（すべての頂点の次数が有限）の場合、タットの条件の一般化が成り立ちます。そのようなグラフが完全マッチングを持つのは、有限部分集合が存在しないときのみであり、有限部分集合を除去すると、部分集合のサイズよりも大きい数の有限奇数成分が生成されます。^[3]

• 二部マッチング
• ホールの結婚定理
• ピーターセンの定理

• Bondy, JA; Murty, USR (1976).グラフ理論とその応用. ニューヨーク: American Elsevier Pub. Co. ISBN 0-444-19451-7。
• Lovász, ラスロー;プラマー医学博士(1986)。マッチング理論。アムステルダム: 北オランダ。ISBN 0-444-87916-1。