What is a necessary condition for a tree to have a Hamiltonian path?

I assume the solution to this question is that a tree can only have two leaves because if there are 3 vertices who have degree 1, then for a path to traverse all vertices, it cannot visit each vertex exactly once. thus cannot be Hamiltonian.

Is that correct?

  • $\begingroup$ I think the only graphs that qualify are expansions of $K_2$, i.e., all vertices along a single line. $\endgroup$ – Connor Harris Dec 3 '18 at 18:42
  • $\begingroup$ if maximum degree is $2$. $\endgroup$ – hbm Dec 3 '18 at 23:44

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.