Prove a lower bound for the maximum matching For a graph $ G $, let $\mu(G)$ denotes the size (in terms of edges) of a maximum matching. I'm supposed to prove that $ \mu(G) \geq n/2 - k/3 $ for a $3$-regular graph $G$ where $ n = V(G) $ and $ k $ is the number of bridges (edges whose deletion add an extra component).
I know Berge-Tutte's formula, which says that $\mu(G) = \min_{S \subseteq V(G)} \frac{1}{2} (n -\text{def}(S)) $. So it seems that I have to show that $ \max_{S \subseteq V(G)} \, \text{def}(S) \leq 2k/3 $. The trouble is that I don't know how to proceed. If you can help, it will much appreciated.
 A: The proof essentially parallels the derivation of Petersen's theorem (that every bridgeless cubic graph has a perfect matching) from Tutte's theorem. If you just read that Wikipedia article, I bet that you can reproduce the rest of my answer on your own.
Let $U$ be any set of vertices of $G$, and partition $V \setminus U$ into $V_1 \cup V_2 \cup \dotsb $ where each $V_i$ induces a connected component of $G-U$. Let $a_i$ be the number of edges between two vertices of $V_i$, and $b_i$ be the number of edges between $V_i$ and $U$. Then 
$$3 |V_i| = \sum_{v \in V_i} \deg v = 2a_i + b_i.$$ 
If $|V_i|$ is odd, that means $b_i$ is odd. There are two possibilities:


*

*$b_i = 1$, which means there is a bridge between $U$ and $V_i$;

*$b_i \ge 3$.


Therefore
$$\sum_{i : |V_i| \text{ odd}} b_i \ge 3 \text{odd}(G-U) - 2k,$$
but on the other hand
$$\sum_{i : |V_i| \text{ odd}} b_i \le 3|U|$$ because there are at most $3|U|$ edges out of $U$. So $3|U| \ge 3\text{odd}(G-U) - 2k$, which gives us exactly the condition
$$\text{def}(U) = \text{odd}(G-U)-|U| \le \frac23 k$$ that you wanted.
