1
$\begingroup$

Let $M$ be a matching in a graph $G$ with an $M$-unsaturated vertex $u$. Prove that if $G$ has no $M$-augmenting path starting at $u$ then $G$ has a maximum matching $L$ such that $u$ is $L$-unsaturated.

Not sure where to start maybe Hall's Thm or Tutte?

$\endgroup$
1
$\begingroup$

Let $S_u=\{M\mid M\textrm{ is a matching with }u\textrm{ is }M\text{ unsaturated and there is no augmenting path starting at }u\}$. $S_u$ is nonempty by the assumption. Take $M^*\in S_u$ with maximum number of edges. Suppose that $M^*$ is not a maximum matching, then there is some augmenting path $P=v_0e_1v_1e_2v_2\dots v_{k-1}e_kv_k$ in $M^*$. By the choice of $M^*$, $u$ cannot be $v_0$ or $v_k$, hence there is some augmenting path $P'$ starting at $u$ in $M^*\triangle P$. If $v_j\notin P'$ for all $j=0,1,\dots,k$, then $P'$ is also in $M^*$, not possible. Thus, let $v_i\in P$ be the first vertex appear in $P'$ when we start walking from $u$ in $P'$. Then either $P'_{[u,v_i]}\cup P_{[v_0,v_i]}$ or $P'_{[u,v_i]}\cup P_{[v_i,v_k]}$ is an augmenting path starting at $u$ in $M^*$, contradiction.

$\endgroup$

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.