塔特定理

在图论中，塔特定理（英語：Tutte theorem）是：

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

图 $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 （俄语）.