Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Petersen's 2-Factor Theorem (1891): A $(2r)$-regular graph can be decomposed into $r$ edge-disjoint $2$-factors.

I'd like to use this theorem (or a more general version of this theorem) to imply the existence of cycles with various properties in arbitrary graphs.

Question: How can Petersen's 2-Factor Theorem be extended e.g. to include non-regular graphs or regular graphs of odd degree?

Perhaps any graph contains $\lfloor d/2 \rfloor$ edge-disjoint $2$-factors, where $d$ is the minimum degree?

share|improve this question
1  
Easy partial lead: For a $(2r+1)$-regular graph $G$, the following are equivalent: (a) $G$ can be decomposed into a $1$-factor and $r$ $2$-factors. (b) $G$ satisfies Tutte's condition - en.wikipedia.org/wiki/Tutte_theorem The Tutte-Berge formula might give a little more info... –  François G. Dorais May 26 '13 at 17:10
1  
simple case of François's comment: cubic graphs only satisfy your perhaps under certain circumstances, e.g. bridgeless. –  Brendan McKay May 26 '13 at 23:57
    
There is also a generalization to directed graphs with the same indegree and outdegree. –  Zsbán Ambrus May 27 '13 at 8:21
add comment

2 Answers

Here is a partial answer to for the case of regular graphs of odd degree which expands on my comment above.

Basic Fact. If $G$ is a $(2r+1)$-regular graph, then $G$ has $r$ edge-disjoint $2$-factors iff $G$ has a $1$-factor.

Indeed, what is left after deleting $r$ edge-disjoint $2$-factors is a $1$-factor. Conversely, after deleting a $1$-factor, what is left is a $2r$-regular graph which has a decomposition into $r$ edge-disjoint $2$-factors by Petersen's theorem.

As I pointed out in the comment above, Tutte's $1$-factor theorem therefore gives an exact characterization of which $(2r+1)$-regular graphs have $r$ edge-disjoint $2$-factors.

Another result of Petersen says that every $2$-edge connected cubic graph has a $1$-factor. (More generarlly, every $2r$-edge connected $(2r+1)$-regular graph has a $1$-factor.) This can be used in the hunt for a counterexample.

Take any cubic graph $G$. Select a vertex $v$ and let $e_1,e_2,e_3$ be the three edges connected to $v$. Insert a new vertex $v_i$ in the middle of $e_i$ and attach from $v_i$ the following graph

 o---o
 |\ /|
 | X o---o
 |/ \|
 o---o

where the vertex of degree 1 on the right is $v_i$.

The resulting graph $H$ is a cubic graph with no $1$-factor (and hence no $2$-factor). Indeed, a $1$-factor $M$ of $H$ would need to contain all three dangling edges from the three copies of the 6-vertex graph pictured above. Therefore, $M$ cannot contain any edge obtained by splitting one of the three edges $e_i$ at $v_i$. So $M$ actually induces a $1$-factor of $G$, but this is impossible since a $1$-factor of $G$ must contain one of $e_1,e_2,e_3$.

Taking $G = K_4$ leads to a counterexample with $22$ vertices. Perhaps a similar trick can be used to produce $(2r+1)$-regular counterexamples for $r \geq 2$?

[I would be very grateful if someone generously volunteered some nice pictures here.]

share|improve this answer
add comment

It sounds like you might be interested into decomposing the edges of your graph into cycles meeting various conditions. With no restrictions, the problem is not interesting since it is necessary and sufficient that your graph is Eulerian (each vertex has even degree). One natural restriction is to insist that each cycle in the decomposition has even length. This will of course only be possible if your graph contains an even number of edges. The first theorem in this direction is due to Seymour, who proved that planar graphs that satisfy the obvious necessary conditions can be decomposed into even length cycles. For certain classes of graphs, one can say more. For example, Hilton and Johnson proved that the complete graph $K_n$ can be decomposed into $p$ 4-cycles, $q$ 6-cycles and $t$ 8-cycles provided $n$ is odd and $4p+6q+8t=\binom{n}{2}$. See the survey On circuit covers, circuit decompositions and Euler tours of graphs by Jackson, or here, or here for more information. I disclose that the last two papers are a shameless plug for recent papers of myself, King, Oum and Verdian-Rizi.

share|improve this answer
add comment

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.