0
$\begingroup$

Define a tournament to be a directed graph such that for any two (distinct) vertices in the graph, there is exactly one edge between them.

I would like to show that a tournament with exactly one Hamiltonian path cannot have a length-three cycle. One approach I'm considering is a proof by contradiction; supposing to the contrary that a tournament with exactly one Hamiltonian path has a three-vertex cycle, then this Hamiltonian path cannot make use of every edge in this cycle. I'd like to show that there exists another Hamiltonian path that does make use of one of these unused edges, though I'm not sure that this is a viable approach.

$\endgroup$
2
$\begingroup$

Call a tournament with $n$ players "qualifying" if there is a unique Hamiltonian path.

Claim all qualifying tournaments are triangle-free.

The claim holds vacuously if $n < 3$.

Proceed by induction on $n$.

Fix a positive integer $n \ge 3$, and suppose the claim holds for all qualifying tournaments with $n-1$ players.

Choose an arbitrary qualifying tournament $T$ with $n$ players, and label the players $P_1,...,P_n$ based on their order in the unique Hamiltonian path.

Thus, for all $i \in \{1,...n-1\}$, $P_i$ beats $P_{i+1}$.

Claim $P_i$ beats $P_n$, for all $i \ne n$.

Suppose otherwise.

Let $i$ be the least positive integer such that $P_n$ beats $P_i$.

By hypothesis, $i \ne n-1$.

If $i=1$, then $$P_n,P_1,...,P_{n-1}$$ is a Hamiltonian path, contradicting uniqueness. Hence $i > 1$.

But then $$P_1,...,P_{i-1},P_n,P_i,...,P_{n-1}$$ is a Hamiltonian path, again contradicting uniqueness.

Therefore $P_i$ beats $P_n$, for all $i \ne n$, as claimed.

But the $(n-1)$-player subtournament $T'$ without $P_n$ is also qualifying, since

  • $T'$ has the Hamiltonian path $P_1,...,P_{n-1}$.$\\[2pt]$
  • If $T'$ had more than one Hamiltonian path, then by appending $P_n$ to each such path, we would have more than one Hamiltonian path for $T$, contradicting uniqueness.

By the inductive hypothesis, $T'$ is triangle-free.

But then if $T$ has a triangle, it would have to include the vertex $P_n$, which is impossible since $P_n$ loses to each of the other players.

It follows that $T$ is triangle-free, which completes the induction, and hence completes the proof.

Moreover, since

  • $T$ is triangle-free.$\\[2pt]$
  • $P_i$ beats $P_{i+1}$ for all $i \in \{1,...n-1\}$.

it follows that $$i < j \implies P_i\;\text{beats}\;P_j$$ hence $T$ is cycle-free, not just triangle-free.

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