3
$\begingroup$

Is it the case that every Hamiltonian bipartite $3$-regular graph has a $4$-cycle?

My intuition says 'yes', because one can form such a graph by taking a $n$-cycle and adding a matching to it. When adding the matching, I think it should be inevitable to form a $4$-cycle eventually, either with edges from the $n$-cycle or with other edges of the matching added previously.

Any ideas on how to show this or how to provide a counterexample?

$\endgroup$

1 Answer 1

6
$\begingroup$

A counterexample is for example Tutte $12$-cage. The Tutte $12$-cage is a bipartite cubic Hamiltonian graph. The length of its smallest cycle is $12$ (as a $12$-cage).

Another example is the Tutte–Coxeter graph.

Finally, the smallest graph with the above properties is the Heawood graph.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .