塔特定理

在图论中，塔特定理（英语：Tutte theorem）是：^[1]

若移除正中央的顶点，则此图分解成三个奇元件，故塔特定理推出此图没有完美匹配。（定理中，取${\displaystyle U}$为仅含该顶点的一元集。）

图 ${\displaystyle G=(V,E)}$有匹配，当且仅当 ${\displaystyle {\text{odd}}(G-U)\leq |U|}$。

其中 ${\displaystyle U\subseteq V}$、${\displaystyle \operatorname {odd} (H)}$是图${\displaystyle 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 （俄语）.