- Tutte-Berge formula
In the
mathematical discipline ofgraph theory the Tutte-Berge formula, named afterWilliam Thomas Tutte andClaude Berge , is a characterization of the size of amaximum matching in a graph. It is a generalization ofTutte's theorem .Tutte-Berge formula
For a given graph G:= left( V, E ight), define u(G) as the size of a maximum matching in G and define o(G) as the number of components in G with an odd number of vertices. The Tutte-Berge formula states that
:u(G) = min_{Usubseteq V} frac{1}{2} left(|V|+|U|-o(G-U) ight).
See also
*
Matching
*Marriage theorem
*Tutte's theorem References
*
*
Wikimedia Foundation. 2010.