Minimum saturation of 3-regular graph

Question

Show that every 3-regular graph on $n$ vertices has a matching which saturates at least $n \Big(1 - \dfrac{1}{4}\Big) = n\dfrac{3}{4}$ vertices.

I generally just need help with this proof, it seems easy, but I don't know where to start.

Answer 1

Let $G=(V,E)$ be a $3$-regular graph of order $n$.

Let $M$ be a matching in $G$ of maximum size $m=|M|$.

Let $S$ be the set of vertices covered by $M$, and let $s=|S|=2m$.

Let $R=V\setminus S$, the set of vertices not covered by $M$, and let $r=|R|=n-s$.

From the fact that $M$ has maximum size, it follow that:
(1) for each vertex $x\in R$ there are $3$ edges between $x$ and $S$;
(2) for each edge $uv\in M$ there are at most $2$ edges between $\{u,v\}$ and $S$.

Counting the number of edges between $R$ and $S$ in two different ways, we see that $3r\le2m=s$, so $\frac rs\le\frac13$ and $$\frac{|S|}{|V|}=\frac s{s+r}=\frac1{1+\frac rs}\ge\frac1{1+\frac13}=\frac34.$$ Therefore $|S|\ge\frac34|V|=\frac34n$.