Dulmage–Mendelsohn decomposition

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.

An edge x,y of the graph G belongs 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.

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.

[5] 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.