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.


Comments are limited to a maximum of 1000 characters.
More information about formatting options