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

  • 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