Tutte–Berge formula

Short description: Characterization of the size of a maximum matching in a graph

In this graph, removing one vertex in the center produces three odd components, the three five-vertex lobes of the graph. Therefore, by the Tutte–Berge formula, it has at most (1−3+16)/2 = 7 edges in any matching.

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).

Statement

The theorem states that the size of a maximum matching of a graph [math]\displaystyle{ G=(V,E) }[/math] equals [math]\displaystyle{ \frac{1}{2} \min_{U\subseteq V} \left(|U|-\operatorname{odd}(G-U)+|V|\right), }[/math] where [math]\displaystyle{ \operatorname{odd}(H) }[/math] counts how many of the connected components of the graph [math]\displaystyle{ H }[/math] have an odd number of vertices.

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

[math]\displaystyle{ \max_{U\subseteq V} \left(\operatorname{odd}(G-U)-|U|\right) }[/math].

Explanation

Intuitively, for any subset [math]\displaystyle{ U }[/math] of the vertices, the only way to completely cover an odd component of [math]\displaystyle{ G-U }[/math] by a matching is for one of the matched edges covering the component to be incident to [math]\displaystyle{ U }[/math]. If, instead, some odd component had no matched edge connecting it to [math]\displaystyle{ U }[/math], 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. Therefore, if some choice of [math]\displaystyle{ U }[/math] 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 [math]\displaystyle{ U }[/math] with the biggest difference between its numbers of odd components outside [math]\displaystyle{ U }[/math] and vertices inside [math]\displaystyle{ U }[/math]. That is, there always exists a subset [math]\displaystyle{ U }[/math] such that deleting [math]\displaystyle{ U }[/math] creates the correct number of odd components needed to make the formula true. One way to find such a set [math]\displaystyle{ U }[/math] is to choose any maximum matching [math]\displaystyle{ M }[/math], and to let [math]\displaystyle{ X }[/math] be the set of vertices that are either unmatched in [math]\displaystyle{ M }[/math], or that can be reached from an unmatched vertex by an alternating path that ends with a matched edge. Then, let [math]\displaystyle{ U }[/math] be the set of vertices that are matched by [math]\displaystyle{ M }[/math] to vertices in [math]\displaystyle{ X }[/math]. No two vertices in [math]\displaystyle{ X }[/math] 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 [math]\displaystyle{ M }[/math]. Every neighbor of a vertex [math]\displaystyle{ x }[/math] in [math]\displaystyle{ X }[/math] must belong to [math]\displaystyle{ U }[/math], for otherwise we could extend an alternating path to [math]\displaystyle{ x }[/math] by one more pair of edges, through the neighbor, causing the neighbor to become part of [math]\displaystyle{ U }[/math]. Therefore, in [math]\displaystyle{ G-U }[/math], every vertex of [math]\displaystyle{ X }[/math] forms a single-vertex component, which is odd. There can be no other odd components, because all other vertices remain matched after deleting [math]\displaystyle{ U }[/math]. So with this construction the size of [math]\displaystyle{ U }[/math] and the number of odd components created by deleting [math]\displaystyle{ U }[/math] are what they need to be to make the formula be true.

Relation to Tutte's theorem

Tutte's theorem characterizes the graphs with perfect matchings as being the ones for which deleting any subset [math]\displaystyle{ U }[/math] of vertices creates at most [math]\displaystyle{ |U| }[/math] odd components. (A subset [math]\displaystyle{ U }[/math] that creates at least [math]\displaystyle{ |U| }[/math] odd components can always be found in the empty set.) In this case, by the Tutte–Berge formula, the size of the matching is [math]\displaystyle{ |V|/2 }[/math]; that is, the maximum matching is a perfect matching. 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.

See also

• Graph toughness, a problem of creating many connected components by removing a small set of vertices without regard to the parity of the components
• Hall's marriage theorem

References

• Berge, C. (1958). "Sur le couplage maximum d'un graphe". Comptes rendus hebdomadaires des séances de l'Académie des sciences 247: 258–259. 
• Berge, C. (1962). The Theory of Graphs. Methuen. Theorem 5, p. 181.  Reprinted by Dover Publications, 2001.
• Bondy, J. A.; Murty, U. S. R. (2007). Graph Theory: An Advanced Course. Graduate Texts in Mathematics. Springer-Verlag. p. 428. ISBN 978-1-84628-969-9. 
• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. New York: North Holland. Exercise 5.3.4, p. 80. ISBN 0-444-19451-7. https://archive.org/details/graphtheorywitha0000bond. 
• Brualdi, Richard A. (2006). Combinatorial Matrix Classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. p. 360. ISBN 0-521-86565-4. https://archive.org/details/combinatorialmat0000brua/page/360. 
• Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1 
• Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag. p. 413. ISBN 3-540-44389-4. https://archive.org/details/combinatorialopt00asch. 
• Tutte, W. T. (1947). "The factorization of linear graphs". Journal of the London Mathematical Society. Series 1 22 (2): 107–111. doi:10.1112/jlms/s1-22.2.107.