1

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?

Community
  • 1
TheNotMe
  • 4,841

1 Answers1

1

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:

A tree must have at least two vertices of degree 1; and if it has exactly two then it is a path graph. For a proof see here.

If the tree has a Hamiltonian path, any vertex of degree 1 must be either a start or end vertex; hence there are at most two such vertices. Thus there are two, the graph is a path, and hence has an Eulerian path.

If the tree has an Eulerian path, there can be at most two vertices of odd degree. Hence there are two, the graph is a path, and hence has a Hamiltonian path.

Community
  • 1
vadim123
  • 82,796