Odd cycles and low oddness

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Gagik
on: January 15th, 2010
Conjecture   If in a bridgeless cubic graph $ G $ the cycles of any $ 2 $-factor are odd, then $ \omega(G)\leq 2 $, where $ \omega(G) $ denotes the oddness of the graph $ G $, that is, the minimum number of odd cycles in a $ 2 $-factor of $ G $.

This conjecture is false.

For odd $ n $ and $ i\in[n] $, let $ H_i $ be the graph obtained by deleting an edge, say $ x_iy_i $, from the Petersen graph. Define $ G_n $ to be the graph obtained by joining vertex $ y_i $ and vertex $ x_{i+1} $ with an edge (with subscripts reduced modulo $ n $). For each $ i\in[n] $, the set $ \{y_{i-1}x_{i},y_ix_{i+1}\} $ is an edge cut. Hence, in any 2-factor of $ G_n $, either none of the edges of the form $ y_ix_{i+1} $ are contained in a cycle, or all of them are contained in the same cycle.

Case 1: If none of the edges described above are contained in a cycle of a 2-factor of $ G_n $, then this 2-factor contains a 2-factor of $ H_i $ for each $ i $. These 2-factors are also 2-factors of the graphs $ H_i+x_iy_i $, that is, each is a 2-factor of the Petersen graph. Each 2-factor of the Petersen graph consists of two cycles of 5 vertices, hence, any such 2-factor of $ G_n $ contains $ 2n $ cycles of odd length.

Case 2: See the comment below.

This conecture is false.

Case 2: If all of the edges of the form $ y_ix_{i+1} $ are contained in the same cycle in a 2-factor of $ G_n $, then replacing the edges $ y_ix_{i+1} $ with the edges $ x_iy_i $ converts this 2-factor of $ G_n $ into a 2-factor of $ n $ disjoint copies of the Petersen graph. Hence, when restricted to each $ H_i $, the 2-factor of $ G_n $ consists of a cycle with 5 vertices and a $ x_iy_i $-path containing a total of 5 vertices. These paths must be joined together through the edges of the form $ y_ix_{i+1} $ creating a cycle of length 5n. Hence, in this case the 2-factor of $ G_n $ contains $ n $ cycles of length 5 and one cycle of length 5n (which is odd).

Now, $ G_n $ is a bridgeless cubic graph whose 2-factors contain only odd cycles, but no 2-factor of $ G_n $ contains fewer than $ n+1 $ cycles.

what is oddness

The notion of oddness of a graph requires explanation.

Let be a bridgeless cubic

Let $ G $ be a bridgeless cubic graph. The oddness of a 2-factor $ F $ is the number of odd circuits of $ F $. The oddness of $ G $ is the smallest oddness over all 2-factors. For example, a 3-edge-colorable cubic graph has oddness zero and the Petersen graph has oddness two.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.