Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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
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$). –  Ekie Nov 12 '11 at 18:05

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

share|improve this answer
    
I did not know that. Thanks. –  echoone Nov 12 '11 at 15:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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