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
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
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)
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.