Alternating path for any given matching?

Let $G=(V,E)$ be a graph, $M$ a matching in $G$. I have read that $M$ is maximal iff there is no augmenting path of $M$ in $G$.

Now consider the graph $G=(\{a_1,b_1,a_2,b_2\},\{a_1b_1,a_2b_2\})$, which is just 4 vertices where two of them are pairwise connected. Now $M=\{a_1b_1\}$ is a matching in $G$, but there is no alternating path to augment it to $M'=\{a_1b_1,a_2b_2\}$, because $G$ does not support any edges for that.

Where is my mistake?

In general, I am trying to proof that given any graph $G$ and some matching $M$ in $G$. Then there always exists an alternating path $P=p_1p_2...p_k, p_i\in V(G)$ w.r.t. to $M$, i.e. $p_1 \not\in V(M)$ and the edges are alternating being in and not in $M$. In the case that $M$ is not maximal, one of these alternating paths is augmenting.

• In your second sentence, it should be maximum, not maximal (for your particular graph, these coincide, however). There is an augmenting path for your graph: $a_2b_2$. – Samuel May 26 '13 at 12:19
• Thanks! I first thought an augmenting path would have to include the first matching, but now noticed that the definition does not require that. – madison54 May 26 '13 at 12:24

There is no restriction that an augmenting path must have length $\ge 2$. In particular, $\{ a_2 b_2 \}$ is an augmenting path in the graph $G = ( \{ a_1,a_2,b_1,b_2 \} , \{ a_1 b_1 , a_2 b_2 \} )$ with matching $M = \{ a_1 b_1 \}$.