Given a tree $T$ with $|V(T)| = n \geq 2$ prove these statements are the same:
- There is an Eulerian path in $T$
- There is a Hamiltonian path in $T$
- The number of leaves in $T$ is $2$
I don't understand how can a tree have an Hamiltonian path, a tree looks like this:
How can you possibly travel on each vertex without crossing it twice? (Statement 2)
I would appreciate if you could help me solve it! Thank you!
$(1)\implies(2)$ since an Eulerian path is a path that includes all edges, and hence includes all vertices because a tree is connected and has no isolated vertex.
$(2)\implies(3)$ since if there is a Hamiltonian path, the $n-2$ intermediate vertices of that path must have degree $\ge2$. The sum of degrees of all vertices should be $2e=2(n-1)=2n-2$ and the sum of degrees of $n-2$ intermediate vertices is $\ge2(n-2)=2n-4$. To enforce connectedness, we require this sum to be exactly $2n-4$ i.e. each intermediate vertex to have degree exactly $2$ and each terminal vertex to have degree exactly $1$.
$(3)\implies(1)$ since the unique path between the two leaves is the required Eulerian path. How? By the above calculation, each internal node has degree exactly $2$. The tree is "linear" so to say -- an unbranched line.