# Dulmage–Mendelsohn decomposition

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958.

## The coarse decomposition

Let G = (U,V,E) 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 DU and their neighbors
• The vertices in DV 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.

## The fine decomposition

The third set of vertices in the coarse decomposition (or all vertices in a graph with a perfect matching) may additionally be partitioned into subsets by the following steps:

• Find a perfect matching of G.
• Form a directed graph H whose vertices are the matched edges in G. For each unmatched edge (u,v) in G, add a directed edge in H from the matched edge of u to the matched edge of v.
• Find the strongly connected components of the resulting graph.
• 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 u and v 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 uv. This edge must belong to a simple cycle in H (by the definition of strong connectivity) which necessarily corresponds to an alternating cycle in G (a cycle whose edges alternate between matched and unmatched edges). This alternating cycle may be used to modify the initial perfect matching to produce a new matching containing edge uv.

An edge uv of the graph G belongs to all perfect matchings of G, if and only if u and v 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.

## Applications

This decomposition has been used to partition meshes in finite element analysis, and to determine specified, underspecified and overspecified equations in systems of nonlinear equations.