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$
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$

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.