塔特定理

若移除正中央的頂點，則此圖分解成三個奇元件，故塔特定理推出此圖沒有完美匹配。（定理中，取$U$為僅含該頂點的一元集。）

在圖論中，塔特定理（英語：Tutte theorem）是：

圖 $G=(V,E)$有匹配，若且唯若 ${\text{odd}}(G-U)\leq |U|$。

其中 $U\subseteq V$、$\operatorname {odd} (H)$是圖$H$的奇數元件的數量（有奇數個頂點的連通元件）。

相關

• 塔特–柏格公式是塔特定理的推廣
• 該定理也是赫爾婚姻定理的推廣（二分圖）

閱讀

• Bondy, J. A. Graph theory with applications. New York: American Elsevier Pub. Co. 1976. ISBN 0-444-19451-7 （俄語）. 
• Lovász, László. Matching theory. Amsterdam: North-Holland. 1986. ISBN 0-444-87916-1 （俄語）.