Existence of a maximum matching containing a vertex $v$ in a graph

Question

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).

Answer 1

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.