Is any tree a Hamiltonian Graph

Question

Hamiltonian path is a graph where every vertex is visited exactly once. And a tree can be anything, like a BST. I think that this answer is no because in a BST, it could find an element before visiting every vertex. Am I right in thinking this?

Answer 1

Consider two vertices joined with a single edge. You can find a Hamiltonian path and it's a tree. Now consider three vertices all joined to a fourth vertex but not joined to each other, a star graph. There is no Hamiltonian path but it's a tree.

Answer 2

Hint

Let $n$ be the number of vertices in the tree. If the tree is Hamiltonian, the Hamiltonian path must contain $n$ vertices and hence $n-1$ edges. But the tree has $n-1$ edges, so the path must contain all vertices and all edges in the tree.

Deduce from here that the tree is a path graph. So any other tree, is not Hamiltonian.

P.S. Alternately, if any vertex has degree at least 3, the tree cannot be Hamiltonian: indeed the path visits each vertex once, so can use at most 2 edges from each vertex.

Answer 3

Your title says "Hamiltonian graph". A Hamiltonian graph is a graph which has a Hamiltonian cycle. A tree is a connected acyclic graph. Since a tree has no cycles, it can't be a Hamiltonian graph.

From the body of your question, it seems that you are asking about Hamiltonian paths, not Hamiltonian cycles. A graph with a Hamiltonian path is not called a Hamiltonian graph (unless it also happens to have a Hamiltonian cycle), it's called a traceable graph.

Can a tree have a Hamiltonian path? Yes, of course, but then the Hamiltonian path has to be the whole tree; if you add one more edge to a Hamiltonian path, then you get a cycle, so you don't have a tree. Thus the only trees with Hamiltonian paths are the path graphs $P_n.$