Proof that if T is Transitive Tournament T Has Unique Hamiltonian Path

1.4k Views Asked by At

A few of us have been looking to prove this but we've been struggling. We've found some proofs online that prove in the wrong direction (if T has unique path then T is transitive).

If you could point us in the right direction or just give us something to work with that would be great just we're completely stumped.

Thanks everyone.

1

There are 1 best solutions below

0
On BEST ANSWER

By the comments, you're satisfied that $T$ has a Hamiltonian path; you just don't know that it's unique.

Suppose $T$ has multiple distinct Hamiltonian paths; label the vertices so there are two paths $H_1=p_1\dots p_n$, $H_2=p_{\pi(1)}\dots p_{\pi(n)}$ where $\pi$ is a non-identity permutation.

Since $T$ is transitive, there is an arc from $p_i$ to $p_j$ whenever $j > i$. Since $\pi$ is a non-identity permutation, there must be some $i, j$ such that $j > i$ but $\pi(i) > \pi(j)$. Can you obtain a contradiction?