For odd and , let be the graph obtained by deleting an edge, say , from the Petersen graph. Define to be the graph obtained by joining vertex and vertex with an edge (with subscripts reduced modulo ). For each , the set is an edge cut. Hence, in any 2-factor of , either none of the edges of the form 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 , then this 2-factor contains a 2-factor of for each . These 2-factors are also 2-factors of the graphs , 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 contains cycles of odd length.
login/create account
Drupal
CSI of Charles University
This conjecture is false.
For odd
and ![$ i\in[n] $](/files/tex/3489ac3673ff1a2165798412b5aaf3c992a55253.png)
, let 
be the graph obtained by deleting an edge, say 
, from the Petersen graph. Define 
to be the graph obtained by joining vertex 
and vertex 
with an edge (with subscripts reduced modulo 
). For each ![$ i\in[n] $](/files/tex/3489ac3673ff1a2165798412b5aaf3c992a55253.png)
, the set 
is an edge cut. Hence, in any 2-factor of 
, either none of the edges of the form 
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
, then this 2-factor contains a 2-factor of 
for each 
. These 2-factors are also 2-factors of the graphs 
, 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 
contains 
cycles of odd length.
Case 2: See the comment below.