Let G = be a bipartite graph, and let D be the set of vertices in G that are not matched in at least one maximum matching of G. Then D is necessarily an independent set, so G can be partitioned into three parts:
The vertices in D ∩ X and their neighbors;
The vertices in D ∩ Y and their neighbors;
The remaining vertices.
Every maximum matching in G consists of matchings in the first and second part that match all neighbors of D, together with a perfect matching of the remaining vertices.
Alternative coarse decomposition
An alternative definition of the coarse decomposition is presented in . Let G be a bipartite graph, M a maximum matching in G, and V0 the set of vertices of G unmatched by M. Then G can be partitioned into three parts:
E - the even vertices - the vertices reachable from V0 by an M-alternating path of even length.
O - the odd vertices - the vertices reachable from V0 by an M-alternating path of odd length.
U - the unreachable vertices - the vertices unreachable from V0 by an M-alternating path.
An illustration is shown on the left. The bold lines are the edges of M. The weak lines are other edges of G. The red dots are the vertices unmatched by M. Based on this decomposition, the edges in G can be partitioned into six parts according to their endpoints: E-U, E-E, O-O, O-U, E-O, U-U. This decomposition has the following properties:
The sets E, O, U are pairwise-disjoint.
The sets E, O, U do not depend on the maximum-matching M.
G contains only O-O, O-U, E-O and U-U edges.
Any maximum-matching in G contains only E-O and U-U edges.
Any maximum-matching in G saturates all vertices in O and all vertices in U.
The size of a maximum-matching in G is |O| + |U| / 2.
For each component of H, form a subset of the Dulmage–Mendelsohn decomposition consisting of the vertices in G that are endpoints of edges in the component.
To see that this subdivision into subsets characterizes the edges that belong to perfect matchings, suppose that two vertices x and y in G belong to the same subset of the decomposition, but are not already matched by the initial perfect matching. Then there exists a strongly connected component in H containing edge x,y. This edge must belong to a simple cycle in H which necessarily corresponds to an alternating cycle in G. This alternating cycle may be used to modify the initial perfect matching to produce a new matching containing edge x,y. An edge x,y of the graph Gbelongs to all perfect matchings of G, if and only if x and y are the only members of their set in the decomposition. Such an edge exists if and only if the matching preclusion number of the graph is one.
Core
As another component of the Dulmage–Mendelsohn decomposition, Dulmage and Mendelsohn defined the core of a graph to be the union of its maximum matchings. However, this concept should be distinguished from the core in the sense of graph homomorphisms, and from the k-core formed by the removal of low-degree vertices.
