= Union of two matchings
In the spanning <subgraph> formed by the union of two <matchings in a graph> $M_1,M_2$, every <vertex> has <vertex degree> at most two. A common <edge> is an isolated two-<vertex> <connected component of a graph>. Every other nontrivial <connected component of a graph> is a <graph path> or an even <graph cycle>, with the <edges> alternating between the two <matchings in a graph>.
Suppose the original <graph> is a <bipartite graph> with <vertex sets> $A,B$, $M_1$ covers a specified <subset> $X\subseteq A$, and $M_2$ covers a specified <subset> $Y\subseteq B$. Their union contains a <matching in a graph> covering $X\cup Y$. On an even <graph cycle>, either alternating choice covers every <vertex>. On an odd-length <graph path>, the larger alternating choice covers every <vertex>. On an even-length <graph path>, both endpoints lie in the same side: choose $M_1$ if they lie in $A$, or $M_2$ if they lie in $B$. Every required endpoint is covered by that choice, and every internal <vertex> meets both choices. Select each common <edge> as well; isolated <vertices> are not in $X\cup Y$. Different <connected components of a graph> do not interfere.
Back to article page
