6
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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... $\endgroup$ May 26, 2013 at 17:10
  • 1
    $\begingroup$ simple case of François's comment: cubic graphs only satisfy your perhaps under certain circumstances, e.g. bridgeless. $\endgroup$ May 26, 2013 at 23:57
  • $\begingroup$ There is also a generalization to directed graphs with the same indegree and outdegree. $\endgroup$ May 27, 2013 at 8:21

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.]

Edit: below is the picture of $H$, as François looked for, if one cannot visualize it merely from the description above.

The Sylvester graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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