# Graph Theory Matchings

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?

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.