Tutte's Matching Theorem

Last updated Nov 1, 2022

Let $G = (V, E)$ be an Undirected Graph. For any $B \subset V$, let $\text{oc}(G[B])$ be the number of Graph Connected Components of $G[B]$ with odd number of vertices. Then $G$ has a Perfect Matching if and only if $\forall A \subset V$, $\text{oc}(G[V \setminus A]) \leq |A|$.

TODO - See Cook - Combinatorial Optimization Ch 5, Section 5.1, pg 131 - 133

• Induced Subgraph
• Set Cardinality