Berge's Theorem states that a matching in a graph, a set of edges sharing no vertex, is of maximum possible size exactly when the graph contains no augmenting path with respect to that matching, an alternating path between two unmatched vertices whose edges switch in and out of the matching along its length. Named for Claude Berge, it is the foundational characterization behind the standard algorithms used to find a maximum matching in a graph by repeatedly searching for and applying augmenting paths.
Facts
StatementA matching M in a graph G has the maximum possible number of edges if and only if the graph contains no augmenting path relative to M, an alternating path that begins and ends at free, unmatched vertices. Proved by Claude Berge in 1957, building on partial observations by Petersen in 1891 and Konig in 1931. 1 Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
In Branch
Source Berge's Theorem (Wikipedia)
Proved By
Source Berge's Theorem (Wikipedia)
Sources
1. Berge's Theorem (Wikipedia)
Wikimedia FoundationLead paragraph, first and second sentences
In graph theory, Berge's theorem states that a matching M in a graph G is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with M.
In Branch: Graph Theory, Lead sentence
In graph theory, Berge's theorem states that a matching M in a graph G is maximum (contains the largest possible number of edges)
Proved By: Claude Berge, Lead paragraph
It was proven by French mathematician Claude Berge in 1957 (though already observed by Petersen in 1891 and Kőnig in 1931).
In Group: Graph Theory, Lead section
In graph theory, Berge's theorem states that a matching M in
View the Source Reader 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.