in G is |O| + |U| / 2. If G has a perfect matching, then all vertices of G are in U. Alternative definition The coarse decomposition Let G = (X+Y,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 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. If G has a perfect matching, then the third set contains all vertices of G. 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 (x,y) in G, add a directed edge in H from the matched edge of x to the matched edge of y. 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 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 (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 x,y. 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