Definitions

# 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\left(V, E right\right)$, define $nu\left(G\right)$ as the size of a maximum matching in $G$ and define $o\left(G\right)$ as the number of components in $G$ with an odd number of vertices. The Tutte-Berge formula states that

$nu\left(G\right) = min_\left\{Usubseteq V\right\} frac\left\{1\right\}\left\{2\right\} left\left(|V|+|U|-o\left(G-U\right)right\right).$