3
$\begingroup$

Every tournament contains a directed Hamiltonian path (a path visiting every vertex exactly once).

Suppose that $T$ is a tournament on $[n]:=\{1,\ldots,n\}$ for some integer $n\geq 2$ with exactly one directed Hamiltonian path. Does this imply that $T$ is isomorphic to the tournament $([n], E)$ where $E = \{(i,j)\in [n]: i<j\}$?

$\endgroup$

1 Answer 1

8
$\begingroup$

It does. Suppose, wlog that the unique Hamiltonian path is $1\to 2\to\cdots\to n$. If $i\to n$ for all $i<n$ then you are done by using the inductive hypothesis on $[n-1]$, otherwise there exists an $i$ such that $n\to i$.

Pick the smallest such $i$ and notice that if $i=1$ then $n\to 1\to 2\to\cdots \to n-1$ is a new Hamiltonian path, and finally if $i>1$ then $1\to 2\to \cdots \to i-1\to n\to i\to \cdots \to n-1$ is a new Hamiltonian path.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .