Tutte-Berge formula

In the mathematical discipline of graph theory the Tutte-Berge formula, named after William Thomas Tutte and Claude Berge, is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte'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

*
*