1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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 have 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.

$\endgroup$
  • $\begingroup$ Indeed. So I am in the wrong direction? $\endgroup$ – TheNotMe Jun 25 '13 at 21:36
  • $\begingroup$ Each of your proofs has correct parts, but is incomplete. $\endgroup$ – vadim123 Jun 25 '13 at 21:37
  • $\begingroup$ I've been still trying and havent been able to reach a correct answer yet... can you help me please? $\endgroup$ – TheNotMe Jun 25 '13 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.