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. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm. Construction The Dulmage-Mendelshon decomposition can be constructed as follows. (it is attributed to who in turn attribute it to ). Let G be a bipartite graph, M a maximum-cardinality matching in G, and V0 the set of vertices of G unmatched by M (the "free vertices"). 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 of V0. Note that V0 is contained in E, since it is reachable from V0 by a path of length 0. 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. Proof: U is disjoint from E and O by definition. To prove that E and O are disjoint, suppose that some vertex v has both an even-length alternating path to an unmatched vertex u1, and an odd-length alternating path to an unmatched vertex u2. Then, concatenating these two paths yields an augmenting path from u1 through v to u2. But this contradicts the assumption that M is a maximum-cardinality matching. The sets E, O, U do not depend on the maximum-cardinality matching M (i.e., any maximum-cardinality matching defines exactly the same decomposition). G contains only O-O, O-U, E-O and U-U edges. Any maximum-cardinality matching in G contains only E-O and U-U edges. Any maximum-cardinality matching in G saturates all vertices in O and all vertices in U. The size of a maximum-cardinality matching