塔特定理

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

在图论中，塔特定理（Template:Lang-en）是：

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

其中 $U\subseteq V$、$\mathrm{odd}(H)$是图$H$的奇数元件的数量（有奇数个頂點的连通元件）。

相关

• 塔特–柏格公式是塔特定理的推广
• 该定理也是赫尔婚姻定理的推广（二分图）

阅读

• Template:Книга
• Template:Книга