The Tutte-Berge Formula gives an exact expression for the size of a maximum matching in an arbitrary graph, generalizing Tutte's Theorem on when a graph has a perfect matching to graphs that may not have one, by computing the largest possible matching through a deficiency formula counting the graph's odd components after removing a suitable vertex set. Named for W. T. Tutte, who proved the perfect-matching case, and Claude Berge, who proved the general formula, it is a foundational result of matching theory in graph theory.
Facts
StatementThe size of a maximum matching in a graph equals one half of the minimum, over all vertex subsets U, of the quantity |U| minus the number of odd components of the graph after removing U, plus the total number of vertices. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Proved By
Source Tutte-Berge formula (Wikipedia)
Source Tutte-Berge formula (Wikipedia)
Sources
1. Tutte-Berge formula (Wikipedia)
Lead paragraph
The Tutte-Berge formula is a characterization of the size of a maximum matching in a graph.
References, Berge 1958 entry
Berge, C. (1958). Sur le couplage maximum d'un graphe. Comptes rendus hebdomadaires des seances de l'Academie des sciences. 247: 258-259.
Proved By: Claude Berge, Lead
It is a generalization of Tutte's theorem on perfect matchings, and is named after W. T. Tutte (who proved Tutte's theorem) and Claude Berge (who proved its generalization).
Proved By: W. T. Tutte, Lead
It is a generalization of Tutte's theorem on perfect matchings, and is named after W. T. Tutte (who proved Tutte's theorem) and Claude Berge (who proved its generalization).
In Group: Graph Theory, Lead section
In the mathematical discipline of graph theory the Tutte-Berge formula is a characterization
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.