Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.