Every 3-regular graph without cut edges has a perfect matching I'm trying to understand Petersen's Theorem as a corollary to Tutte's Theorem.
Corollary 5.4.  Every 3-regular graph without cut edges has a
perfect matching.
Proof. Let $G$ be a 3-regular graph without cut edges, and let $S$
be a proper subset of $V$. Denote by $G_1, G_2, \dots, G_n$ the odd
components of $G - S$ and let $m_i$ be the number of edges with one
end in $G_i$ and one end in $S, 1 \leq i \leq n.$ Since $G$ is
3-regular
\begin{align}
        \sum_{v \in G_i} d(v) &= 3 |(G_i)|, \tag{5.8}
\end{align}
for $1 \leq i \leq n$ and
\begin{align}
        \sum_{v \in S} d(v) &= 3 |S|. \tag{5.9}
\end{align}
By equation (5.8), $m_i = \sum_{v \in G_i} d(v) - 2 \epsilon(G_i)$ is odd, where $\epsilon(G_i)$ is the number of edges in $G_i$. Now $m(i) \neq 1$ since $G$ has no cut edges.  Thus $m_i \geq 3$ for $1 \leq i \leq n$.  It follows that
\begin{align}
   o(G - S) = n \leq 1/3 \sum_{i=1}^n m_i \leq 1/3 \sum_{v \in S} d(v) = |S|
\end{align}
Therefore by Tutte's Theorem, G has a perfect matching.
Question.  I can see that $m_i$ as given by the expression $\sum_{v \in G_i} d(v) - 2 \epsilon(G_i)$ is odd whenever $G_i$ is an odd component.  (I can also see that $m_i$ is even whenever $G_i$ is even.  I can prove both facts.  But I can't see how the equation $m_i = \sum_{v \in G_i} d(v) - 2 \epsilon(G_i)$ was deduced from equation 5.8.
I know that $\sum d(v) = 2 \epsilon(G_i)$.  That's theorem 1.1 in the book.  (The sum of the degrees of a graph equals 2 times its number of edges.  A very intuitive theorem.)  But I can't connect this fact and equation 5.8 to give the expression for $m_i$.  Any direction is appreciated. Thank you.
 A: When we take the sum $$\sum_{v \in G_i} d(v)$$ (keeping in mind that $d(v)$ is $v$'s degree in $G$, not in $G_i$) then every edge with two endpoints in $G_i$ is counted twice, and every edge with one endpoint in $G_i$ is counted only once.


*

*There are $\epsilon(G_i)$ edges with two endpoints in $G_i$, so they contribute $2\epsilon(G_i)$ to the value of the sum. 

*The edges with one endpoint in $G_i$ are precisely the edges between $G_i$ and $S$ (there are, by definition, no edges between $G_i$ and $G_j$ for $i \ne j$) so they contribute $m_i$ to the sum.


So we get $$3|G_i| = \sum_{v \in G_i} d(v) = 2 \epsilon(G_i)+ m_i$$ and then you know what to do from there.

Later on, we need the inequality
$$3|S| = \sum_{v \in S} d(v) \ge \sum_{i=1}^n m_i$$
which follows for similar reasons. In the sum of $d(v)$ over all $v \in S$, there are three types of edges to consider:


*

*Edges internal to $S$, which would be counted twice, but which we just throw away in the inequality.

*Edges going from $S$ to $G_i$ for some $i$ of which there are exactly $m_i$; 
each is counted in the sum once.

*Edges going from $S$ to some even component of $G - S$, which we also throw away.

