I need to prove that $|M| \leq |W| \leq 2|M|, \forall G$ where $G$ is a graph, $M$ is a maximum matching for $G$ and $W$ is a minimum vertex cover for $G$. I have proven $|M| \leq |W|$ and have shown that if $2|M|$ vertices in $W$ are matched (this would be all of the matched vertices), there can be no more vertices in $W$. I am struggling to show that if not all of the matched vertices are in $W$ then there can not be $2|M| < |W|$. I have tried to think of the problem in many different ways but have come up short. I feel like the fact that unmatched vertices in $W$ must be adjacent to at least one matched vertex not in $W$ is important somehow but I don't know how to take it further.
Thank you for the help.
Best Answer
In a maximum matching $M$, all unmatched vertices cannot be connected to each other – two adjacent unmatched vertices could be connected by an edge that can then be added to $M$, contradicting its maximality.
Thus, assuming the graph is connected and has at least one edge, every unmatched vertex is adjacent to some vertex incident to an edge in $M$.
The set of all vertices incident to edges in $M$ has cardinality $2|M|$ and forms a vertex cover for the graph by the above argument, showing $|W|\le2|M|$.