Existence of a maximum matching containing a vertex $v$ in a graph Let $v$ be a vertex of a graph $G$, which is not isolated.
Prove the existence of a maximum matching in which $v$ is saturated (matched).
 A: Note: "Prove the existence of a maximum matching."  That is not to say that every maximum matching saturates $v$ (it is possible that some do not).
Consider any maximum matching, $M$ (guaranteed to exist).  Either $v$ is saturated in $M$ or it isn't.  If it is, then we are done and the matching we are looking at satisfies the claim.
Suppose then that $v$ is not saturated in $M$.  As $v$ is not isolated, it has at least one neighbor.  Pick one such neighbor and label it $u$.  All of $v$'s neighbors, and in particular $u$, must be saturated (for if not then by adding the edge $uv$ to the matching $M$ we will increase the number of matched edges, contradicting that $M$ is maximum).  Suppose the edge in the matching saturating $u$ is labeled $ux$.
Consider what happens if you remove $ux$ from the matching and add instead $uv$.  This is again a valid matching since there is still at most one matched edge next to any vertex since $v$ was previously unsaturated and $u$ is still adjacent to exactly one matched edge while all other vertices remain the same as in $M$ with the exception of $x$ which became unsaturated.  This new matching, $M'$, has the same number of edges as $M$ and so is also maximum.
