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.
Best Answer
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 \}$.