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.

  • $\begingroup$ Is not that Petersen theorem. You need Tutte theorem to prove it, no? $\endgroup$ – Aqua Nov 6 '17 at 16:41
  • $\begingroup$ 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. $\endgroup$ – 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.
  • $\begingroup$ 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.) $\endgroup$ – P. White Nov 6 '17 at 18:45
  • $\begingroup$ 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$.) $\endgroup$ – Misha Lavrov Nov 6 '17 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.