Prove that in a tree graph $T$, a path is a hamilton path iff it is an euler path.
so I said this:
==>: Let $<x_1,x_2,…,x_n>$ be a hamilton path and let us suppose by contradiction that it is not an euler path. Then there is an edge that starts in a vertix $x_i$ that we visit twice or more, as in $<x_1,x_2,…,x_i,…,x_k,x_i,…,x_n>$, and then we have a circle $<x_i,…,x_k,x_n>$, in contradiction that $T$ is a tree.
<==: Let $<x_1,x_2,…,x_k>$ be an euler path in the tree. An euler path passes through all the edges. A tree is connected, and the degree of any vertix is $\geq 1$, so this euler path has to visit every vertix $x_i$ in the graph in order to get into it and exit out of it, thus it is a hamilton path.
Is this proof good enough?
Best Answer
Your proof of $\rightarrow$ assumes that failure to be an Euler path implies that some edge is visited more than once. This is incorrect, as some edge might not be visited at all.
Your proof of $\leftarrow$ assumes that a path that visits every vertex must be a Hamilton path. This is incorrect, as you also need to prove that it visits every vertex only once.
As requested, here's a solution to the problem: