# Odd cycles and low oddness

 Importance: Medium ✭✭
 Author(s):
 Subject: Graph Theory
 Keywords:
 Posted by: Gagik on: January 15th, 2010

\begin{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$. \end{conjecture}

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