# Does there exist a tournament with exactly two Hamiltonian paths

combinatoricsdirected graphsgraph theoryhamiltonian-path

A tournament is a complete directed graph. A Hamiltonian path is a path that crosses each vertex exactly once.

My conjecture is no. I have tried using induction, proof by contradiction, all to no avail. I understand that the tournament must contain at least one Hamiltonian path, and the tournament also cannot have a Hamiltonian cycle hence must not be strongly connected; but I do not seem to be able to make a breakthrough using the tools at hand.

• The strongly connected components of the tournament $$T$$: a partition of the vertices of $$T$$ into subsets $$C_1, \dots, C_k$$ such that for vertices $$u$$ and $$v$$, there is both a $$u \to v$$ path and a $$v \to u$$ path exactly when $$u,v$$ are in the same subset $$C_i$$.
• The condensation of $$T$$: the directed graph with vertices $$C_1, C_2, \dots, C_k$$, and an arc $$(C_i, C_j)$$ whenever there is an arc $$u,v$$ with $$u \in C_i, v \in C_j$$ in the original graph $$T$$.
These can both be defined for general directed graphs. The condensation is always acyclic, and when $$T$$ is a tournament, it is the unique acyclic $$k$$-vertex tournament. We can order the vertices $$C_1, C_2, \dots, C_k$$ such that whenever $$i, there is an arc $$(C_i, C_j)$$ in the condensation of $$T$$.
With this setup, any Hamiltonian path in $$T$$ must start in $$C_1$$ and end in $$C_k$$. You should be able to describe what it looks like, when there is only one option for the Hamiltonian path, and when (and how) there are multiple options. In particular, it will follow that when there's more than one Hamiltonian path, there must be at least three.