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.
Best Answer
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.
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: