# 3-regular graphs with no bridges

Problem. Use Tutte's 1-factor theorem to prove that every 3-regular graph with no bridges has a 1-factor.

I honestly have no idea how to approach this problem. I have drawn a couple of graphs to gain some insight to no avail. Any hints or tips will be greatly appreciated.

-

## 2 Answers

Hint: To use Tutte's theorem, we must show that the graph satisfies Tutte's condition; that is, for any $S\subset V(G)$, we must show that $q(G-S) \leq |S|$, where $q(G-S)$ denotes the number of odd components in $G-S$. Consider an arbitrary set $S\subset V(G)$ and look at an odd component $C$ of $G-S$. What can you say about the number of edges running between $C$ and $S$?

-
Since every vertex in $S$ has degree 3, there can be at most 3|S| edges running between $C$ and $S$. Also, if a vertex in $C$ has degree 1 (or 2), then there must be 2 (or 1) edges from that vertex going to $S$. I am not sure how the fact that $C$ is odd plays a role exactly. – echoone Nov 12 '11 at 5:18
Note that the sum of the degrees in $C$ must be odd in $G-S$ (why?). However, a component is also itself a graph, and since graphs must always have an even degree sum, the degree sum in $C$ (when only considering edges in $C$) must be even. Hence, in $G-S$, an odd number of edges must be sent from every odd component to $S$. Can there only be one edge between an odd component and $S$? – Ekie Nov 12 '11 at 6:03
Sorry, where I said "$G-S$" in the previous comment, I should have said "$G$". – Ekie Nov 12 '11 at 6:13
I don't understand why the sum of the degrees in $C$ must be odd in $G-S$. For example, suppose $G = K_4$ and $|S|=3$. Then $G-S$ has only one component consisting of one vertex, so the sum of the degrees is 0. – echoone Nov 12 '11 at 15:29
I left another comment correcting that; I had meant $G$ rather than $G-S$. In your example, $G-S$ has one odd component (a single vertex), but the degree of that single vertex is 3 in $G$. The argument above holds if you change $G-S$ to $G$ (in both places). There must be an odd number of edges running between $S$ and each odd component of $G-S$ -in $G$- since $G$ is 3-regular. Furthermore, there cannot be a single edge running between $S$ and an odd component, since $G$ has no bridge. Thus, there are at least $3q(G-S)$ edges running between $S$ and all of the components of $G-S$ (in $G$). – Ekie Nov 12 '11 at 18:05

What your are being asked to prove is sometimes known as Petersen's Theorem.

-
I did not know that. Thanks. – echoone Nov 12 '11 at 15:31