Gallai–Edmonds decomposition

An illustration of the three sets in the Gallai–Edmonds decomposition of an example graph.

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 $G$, its Gallai–Edmonds decomposition consists of three disjoint sets of vertices, $A(G)$, $C(G)$, and $D(G)$, whose union is $V(G)$: the set of all vertices of $G$. First, the vertices of $G$ are divided into essential vertices (vertices which are covered by every maximum matching in $G$) and inessential vertices (vertices which are left uncovered by at least one maximum matching in $G$). The set $D(G)$ is defined to contain all the inessential vertices. Essential vertices are split into $A(G)$ and $C(G)$: the set $A(G)$ is defined to contain all essential vertices adjacent to at least one vertex of $D(G)$, and $C(G)$ is defined to contain all essential vertices not adjacent to any vertices of $D(G)$.

It is common to identify the sets $A(G)$, $C(G)$, and $D(G)$ with the subgraphs induced by those sets. For example, we say "the components of $D(G)$" to mean the connected components of the subgraph induced by $D(G)$.

The Gallai–Edmonds decomposition has the following properties:

1. The components of $D(G)$ are factor-critical graphs: each component has an odd number of vertices, and when any one of these vertices is left out, there is a perfect matching of the remaining vertices. In particular, each component has a near-perfect matching: a matching that covers all but one of the vertices.
2. The subgraph induced by $C(G)$ has a perfect matching.
3. Every subset $X\subseteq A(G)$ has neighbors in at least $|X|+1$ components of $D(G)$.
4. Every maximum matching in $G$ has the following structure: it consists of a near-perfect matching of each component of $D(G)$, a perfect matching of $C(G)$, and edges from all vertices in $A(G)$ to distinct components of $D(G)$.
5. If $D(G)$ has $k$ components, then the number of edges in any maximum matching in $G$ is ${\frac {1}{2}}(|V(G)|-k+|A(G)|)$.

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