# 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, ..., 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.

• Is not that Petersen theorem. You need Tutte theorem to prove it, no? – Aqua Nov 6 '17 at 16:41
• That's correct. This is a corollary to Tutte's theorem. I'd invoke Tutte's very soon. But I didn't understand that expression for $m_i$ yet. – P. White Nov 6 '17 at 16:47

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.
• I'm now at the last step. I can't see why $o(G - S) = n <= 1/3 \sum m(i).$ (I'll add the rest of the proof to the question.) – P. White Nov 6 '17 at 18:45
• Simply because $m_i \ge 3$ for all $i$, so $\sum_{i=1}^n m_i \ge 3n$. (We rule out $m_i = 1$ because $G_i$ has no cut edges, we rule out $m_i = 2$ because $m_i$ is odd, so we must have $m_i \ge 3$.) – Misha Lavrov Nov 6 '17 at 18:56