3-regular graph maximum matching I'm trying to prove that any 3-regular undirected simple graph has a matching that covers at least $(\frac{7}{8}) |V(G)|$ vertices.
I know Petersen's Theorem, and have understood its proof. I think, it should be possible to modify the proof by considering the number of possible bridges and using the Tutte–Berge formula, but unfortunately I was not able to find a concrete argument, so I am thankful for any help with this problem.
 A: To apply Tutte-Berge, we want to find a small set $U \subseteq V$ such that $G[V-U]$ has many odd components. There are two limitations on the number of odd components:


*

*In an $n$-vertex graph, there are at most $n-|U|$ vertices to be split up between the odd components.

*There are at most $3|U|$ edges from $U$ to the odd components, and each component needs some number of those edges.


Based on the second constraint, we can consider two kinds of odd components. Odd components of $G[V-U]$ with $1$ or $3$ vertices must have at least $3$ edges to $U$ (just by counting the maximum number of edges within a component), and odd components with at least $5$ vertices still must have at least $1$ edge to $U$ (since you can't have an odd component by itself in a $3$-regular graph). 
Let $u = |U|$, let $x$ be the number of small odd components, and let $y$ be the number of large odd components. Then the two constraints are $$x + 5y \le n-u \qquad \text{and} \qquad 3x + y \le 3u.$$
Combining these with weights $\frac18$ and $\frac38$, we get $\frac54x + y \le \frac18n + u$, so $x + y \le \frac18 n + u$ as well. By the Tutte-Berge formula, the number of vertices covered by a maximum matching is the minimum of $n+u-x-y$ over all sets $U$, and we've shown that this always satisfies
$$
   n + u - x - y \ge n + u - (\tfrac18 n + u) = \tfrac78 n
$$
So the matching covers at least $\frac78n$ vertices.
