在圖論學科中，塔特定理是具有perfect matching的圖的一個表征。將二部圖的霍爾定理推廣到任意圖。它是Tute-Berge公式的一個特例。
基本介紹
定義,塔特-伯格公式,推導過程,
定義
圖 G=(V,E) 有perfect matching若且唯若滿足 ∀U⊆V,o(G−U)≤|U|,o(X) 表示 X 子圖的奇連通塊數。
塔特-伯格公式
一個圖G=(V,E)的最大匹配的大小等於
Tutte-Berge Formula
其中odd(G-U)表示這個圖當中有多少個聯通分量具有奇數個頂點。
推導過程
必要性：
如果 G 有perfect matching，那么每個奇連通塊至少有一個點需要與 U 中的點匹配，故得證.
充分性：
定義壞集 S 滿足，
|S| ＜ o(G−S) |S| ＜ o(G−S)
那么圖 G 中不能存在壞集。
如果 S 是 G 的壞集，那么 S 也一定是 G 的導出子圖的壞集。
於是不妨令 G 滿足 G 不存在perfect matching，且加入任意一條不在 G 中的邊後存在perfect matching。
令 S 為滿足度數為 |V|−1|V|−1 的點集，首先考慮 G−SG−S 中的每個連通塊都是團的情況，容易發現 S 一定是壞集。
於是 G−SG−S 中至少有一個連通塊不是團，考慮把這個連通塊扯出來討論，找出其中兩個沒有邊直接相連的點 x,yx,y ，設從 x→yx→y 最短路上的頭三個點為 a,b,ca,b,c ，那么顯然 (a,c)∉E(a,c)∉E ，且一定存在點 dd 滿足 (b,d)∉E(b,d)∉E。
由於上面限制了 G 加入任意一條不在 G 中的邊後都存在perfect matching，因此設 M1M1 是 (V,E∪(a,c))(V,E∪(a,c)) 的一組perfect matching， M2M2 是 （V,E∪(b,d)）（V,E∪(b,d)）的一組perfect matching，顯然 (a,c)∈M1,(M2)∈M2(a,c)∈M1,(M2)∈M2 （第一次走 M1M1 的）。
然後定義 P 是在 G 上面從 d 出發，交替走 M1,M2M1,M2 中的邊得到的最長路徑，顯然最後會落在 a,b,ca,b,c 點中的一個。
如果落在 b 點，令 C=P∪(b,d)C=P∪(b,d) ，否則令 C=P∪(a/c,b)∪(b,d)C=P∪(a/c,b)∪(b,d) ，這樣 C 就是一個偶環，對於 C 選擇不在 M2M2 中的邊可以形成一組新的匹配，對於 G−CG−C 中的點按照 M2M2 中的邊匹配，這樣就形成了一組新的perfect matching，故得證。
