Abhijeet Mulgund's Personal Webpage

Search

Search IconIcon to open search

Tutte-Berge Formula

Last updated Nov 1, 2022

# Statement

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 $$\nu(G) = \min {\frac{1}{2} \Big(|V| - \text{oc}(G[V \setminus A] + |A|\Big) : A \subset V}$$

# Proof

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

# Other Outlinks