Partition of the vertices of a graph giving information on the structure of maximum matchings
In graph theory, the Gallai–Edmonds decomposition is a partition of the vertices of a graph into three subsets which provides information on the structure of maximum matchings in the graph. Tibor Gallai and Jack Edmonds independently discovered it and proved its key properties.
The Gallai–Edmonds decomposition of a graph can be found using the blossom algorithm.
Properties.
Given a graph formula_1, its Gallai–Edmonds decomposition consists of three disjoint sets of vertices, formula_2, formula_3, and formula_4, whose union is formula_5: the set of all vertices of formula_1. First, the vertices of formula_1 are divided into "essential vertices" (vertices which are covered by every maximum matching in formula_1) and "inessential vertices" (vertices which are left uncovered by at least one maximum matching in formula_1). The set formula_4 is defined to contain all the inessential vertices. Essential vertices are split into formula_2 and formula_3: the set formula_2 is defined to contain all essential vertices adjacent to at least one vertex of formula_4, and formula_3 is defined to contain all essential vertices not adjacent to any vertices of formula_4.
It is common to identify the sets formula_2, formula_3, and formula_4 with the subgraphs induced by those sets. For example, we say "the components of formula_4" to mean the connected components of the subgraph induced by formula_4.
The Gallai–Edmonds decomposition has the following properties:
Construction.
The Gallai–Edmonds decomposition of a graph formula_1 can be found, somewhat inefficiently, by starting with any algorithm for finding a maximum matching. From the definition, a vertex formula_37 is in formula_4 if and only if formula_39 (the graph obtained from formula_1 by deleting formula_37) has a maximum matching of the same size as formula_1. Therefore we can identify formula_4 by computing a maximum matching in formula_1 and in formula_39 for every vertex formula_37. The complement of formula_4 can be partitioned into formula_2 and formula_3 directly from the definition.
One particular method for finding a maximum matching in a graph is Edmonds' blossom algorithm, and the processing done by this algorithm enables us to find the Gallai–Edmonds decomposition directly.
To find a maximum matching in a graph formula_1, the blossom algorithm starts with a small matching and goes through multiple iterations in which it increases the size of the matching by one edge. We can find the Gallai–Edmonds decomposition from the blossom algorithm's work in the last iteration: the work done when it has a maximum matching formula_51, which it fails to make any larger. 
In every iteration, the blossom algorithm passes from formula_1 to smaller graphs by contracting subgraphs called "blossoms" to single vertices. When this is done in the last iteration, the blossoms have a special property: 
The first property follows from the algorithm: every vertex of a blossom is the endpoint of an alternating path that starts at a vertex uncovered by the matching. The second property follows from the first by the lemma below:
 Let formula_1 be a graph, formula_51 a matching in formula_1, and let formula_56 be a cycle of length formula_57which contains formula_33 edges of formula_51 and is vertex-disjoint from the rest of formula_51. Construct a new graph formula_61 from formula_1 by shrinking formula_56 to a single vertex. Then formula_64 is a maximum matching in formula_61 if and only if formula_51 is a maximum matching in formula_1. 
This lemma also implies that when a blossom is contracted, the set of inessential vertices outside the blossom remains the same.
Once every blossom has been contracted by the algorithm, the result is a smaller graph formula_61, a maximum matching formula_69 in formula_61 of the same size as formula_51, and an alternating forest formula_72 in formula_61 with respect to formula_69. In formula_61, the Gallai–Edmonds decomposition has a short description. The vertices in formula_72 are classified into inner vertices (vertices at an odd distance in formula_72 from a root) and outer vertices (vertices at an even distance in formula_72 from a root); formula_79 is exactly the set of inner vertices, and formula_80 is exactly the set of outer vertices. Vertices of formula_61 that are not in formula_72 form formula_83.
Contracting blossoms preserves the set of inessential vertices; therefore formula_4 can be found from formula_80 by taking all vertices of formula_1 which were contracted as part of a blossom, as well as all vertices in formula_80. The vertices in formula_2 and formula_3 are never contracted; formula_90 and formula_91.
Generalizations.
The Gallai–Edmonds decomposition is a generalization of Dulmage–Mendelsohn decomposition from bipartite graphs to general graphs.
An extension of the Gallai–Edmonds decomposition theorem to multi-edge matchings is given in Katarzyna Paluch's "Capacitated Rank-Maximal Matchings".
References.
 ;templatestyles src="Reflist/styles.css" / ;