8
$\begingroup$

Here's a quickie:

Let $r\ge2$. Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle?

I've been playing around with this for almost an hour, but I can't prove it.

$\endgroup$
8
$\begingroup$

The Horton graph is cubic, 3-connected, bipartite, and non-Hamiltonian. There is a conjecture of Barnette (see here) that cubic, 3-connected, bipartite, planar graphs are Hamiltonian. This has yet to be proven or disproven.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.