Tutte–Berge formula

In the mathematical discipline of graph theory the Tutte–Berge formula is a characterization of the size of a maximum matching in a graph.

It is a generalization of Tutte theorem on perfect matchings, and is named after W. T. Tutte (who proved Tutte's theorem) and Claude Berge (who proved its generalization).

The theorem states that the size of a maximum matching of a graph

counts how many of the connected components of the graph

have an odd number of vertices.

Equivalently, the number of unmatched vertices in a maximum matching equals

of the vertices, the only way to completely cover an odd component of

If, instead, some odd component had no matched edge connecting it to

, then the part of the matching that covered the component would cover its vertices in pairs, but since the component has an odd number of vertices it would necessarily include at least one leftover and unmatched vertex.

has few vertices but its removal creates a large number of odd components, then there will be many unmatched vertices, implying that the matching itself will be small.

This reasoning can be made precise by stating that the size of a maximum matching is at most equal to the value given by the Tutte–Berge formula.

The characterization of Tutte and Berge proves that this is the only obstacle to creating a large matching: the size of the optimal matching will be determined by the subset

with the biggest difference between its numbers of odd components outside

creates the correct number of odd components needed to make the formula true.

is to choose any maximum matching

be the set of vertices that are either unmatched in

, or that can be reached from an unmatched vertex by an alternating path that ends with a matched edge.

can be adjacent, for if they were then their alternating paths could be concatenated to give a path by which the matching could be increased, contradicting the maximality of

, for otherwise we could extend an alternating path to

forms a single-vertex component, which is odd.

There can be no other odd components, because all other vertices remain matched after deleting

and the number of odd components created by deleting

are what they need to be to make the formula be true.

Tutte's theorem characterizes the graphs with perfect matchings as being the ones for which deleting any subset

odd components can always be found in the empty set.)

In this case, by the Tutte–Berge formula, the size of the matching is

Thus, Tutte's theorem can be derived as a corollary of the Tutte–Berge formula, and the formula can be seen as a generalization of Tutte's theorem.