0
$\begingroup$

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 2

1

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$?

  • 0
    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.2011-11-12
  • 0
    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$?2011-11-12
  • 0
    Sorry, where I said "$G-S$" in the previous comment, I should have said "$G$".2011-11-12
  • 0
    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.2011-11-12
  • 1
    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$).2011-11-12
1

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

  • 0
    I did not know that. Thanks.2011-11-12