Enumerating the graphs upto $9$ vertices and the cubic connected graphs upto $18$ vertices, I did not find a graph with minimum degree $\ge 3$ and exact $1$ hamilton circuit.

  • Is there a graph with this property ?
  • If yes, which one is the smallest ?
  • 2
    $\begingroup$ A beautiful result due to Andrew Thomason states that if every vertex of a graph has odd degree, then every edge is contained in an even number of Hamiltonian cycles. So you certainly won't find what you're looking for amongst the cubic graphs. $\endgroup$ – Casteels Oct 6 '14 at 14:21
  • $\begingroup$ A very nice partial result! $\endgroup$ – Peter Oct 7 '14 at 21:30

Your Answer

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

Browse other questions tagged or ask your own question.