I had an exam and there was the following question:
$\mathcal{A}$ and $\mathcal{B}$ are matchings in a graph $G$, with $|\mathcal{A}|< |\mathcal{B}|$, study the graph formed with the edges of $\mathcal{A}\cup \mathcal{B}$ to prove that there is at least one augmenting path to $\mathcal{A}$.
I've read a bit about matchings in some books, I've read Berge's theorem:
- Let $M$ be a matching in a graph $G$, $M$ is maximum iff $G$ contains no $M$-augmenting paths.
And I guess I could formulate an answer with that. But I couldn't think of what would happen in $\mathcal{A}\cup \mathcal{B}$ that would indicate that there is at least augmenting path in $\mathcal{A}$.
Let's think of edges in $\mathcal{A}$ as being coloured red, and the edges in $\mathcal{B}$ as being coloured blue. Notice that $\mathcal{A}\cup\mathcal{B}$ is a disjoint union of paths of length $1$ (i.e., corresponding to edges that are in both $\mathcal{A}$ and $\mathcal{B}$), paths of length $\geq 2$, and cycles, where for each cycle or path of length $\geq 2$, the edges alternate colours.
Now if $P$ is a path in $\mathcal{A}\cup\mathcal{B}$ of odd length at least $3$, then the first and last edges of $P$ have the same colour. If the colour is blue, then $P$ is an augmenting path for $\mathcal{A}$.
On the other hand, can you see that if $|\mathcal{A}|<|\mathcal{B}|$, then there must be at least one path of odd length $\geq 3$ whose first and last edge is coloured blue?