Dulmage–Mendelsohn decomposition - a simple example

Question

I am trying to understand what the Dulmage–Mendelsohn decomposition is all about. I read some pages but did not find any simple example, which makes it hard for me to understand. In particular, consider the following very simple bupartite graph, with two nodes in each side:

\begin{matrix} x_1 &\to& y_1 \\ & \searrow & \\ x_2 & & y_2 \end{matrix}

The definition of the decomposition requires "the set of vertices in G that are not matched in at least one maximum matching of G"; since $x_1$ is matched in every maximum matching of G, the set $D$ contains the vertices $x_2,y_1,y_2$. So the three parts in the decomposition are:

• $D\cap X$ and their neighbors, i.e., $\{x_2\}$.
• $D\cap Y$ and their neighbors, i.e., $\{y_1,y_2,x_1\}$.
• The remaining vertices - an empty set.

The theorem says that "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". But, I do not see how is this true in the above example.

Is my example correct?

Answer 1

I don't see where is the problem : The only maximum matchings of your graph are $\{x_1y_1\}$ and $\{x_1y_2\}$, that we can obtained as

• A matching from the first part : $\emptyset$
• A matching from the second part : $\{x_1,y_i\}$, matching $x_1$ the only (open) neighbour of $D$
• A perfect matching from the third part : $\emptyset$