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.

  • 3
    $\begingroup$ 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$. $\endgroup$ – Samuel May 26 '13 at 12:19
  • $\begingroup$ Thanks! I first thought an augmenting path would have to include the first matching, but now noticed that the definition does not require that. $\endgroup$ – 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 \}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.