MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.

Kelman claims that this conjecture is equivalent to a stronger one, which imposes some restrictions on the Hamiltonian cycles. The statement of this equivalence lies in his paper, "Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles", AMS Translations, Series 2 158, pp. 127–140.

It is Theorem 17 in this paper.

Unfortunately, Kelmans does not even give a sketch of the proof. I have read in detail the paper, but was not able to reconstruct the proof.

So I would like to know if :

1) these details are written somewhere.

2) is it true that if a Barnette graph is Hamiltonian, then Kelman's conditions can be imposed on that very graph (without any more assumption).

Thank you.

share|cite|improve this question
Ok, I got it. Kelmans' idea is to use a hypothetical counterexample to the strong conjecture as a building block to construct a (huge) counterexample to the usual Barnette conjecture. Hence his work does not give a positive answer to Question 2). Question 2) remains interesting to me. – Arnaud Mortier Jun 26 '13 at 14:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.