Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:

$\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

For context, this came from an observation that the inductive construction in the above page seems to be equivalent to insertion sort using the given order. Is it possible to use other sorting algorithms?

  • 1
    $\begingroup$ Perhaps my question about random orders may be relevant. It depends on what you mean by work, but it was decided most would actually get something done. $\endgroup$ Jul 8, 2012 at 5:16
  • $\begingroup$ do you need make a tree that each node is reachable with(O(1)) in your tournament graph? $\endgroup$
    – amin k
    Jul 10, 2012 at 12:26

1 Answer 1


I assume that you intend $\leq$ to be the reflexive and transitive closure of $E$, or directed reachability, that is $\leq$ is really the smallest fixpoint of the equivalence you give:

$\qquad \displaystyle a \leq b \iff \exists\, v_0 \dots v_n. a \to v_o \to \dots \to v_n \to b$

with $n \geq 0$ and $v \to u \iff (v,u) \in E$.

The key argument here is that $\leq$ is indeed a total order. If it is, you can use it for sorting, and the result is by definition of $\leq$ a Hamiltonian path: consider the result of the sort $v_1 \dots v_n$. If there were no edge between $v_i$ and $v_{i+1}$, by $V_s = v_i \leq v_{i+1}$ there is $v \in V$ such that $v_i \leq v \leq v_{i+1}$. This contradicts that $\leq$ is a (total) order and $V_s$ is sorted with respect to $\leq$.

Unfortunately, $\leq$ is not an order relation: it is not antisymmetric. Consider the small tournament based on $K_4$:

counter example

Here, $a \leq d$ and $d \leq a$ (directed cycles are the culprits!) but $a \neq d$. So $\leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.

  • $\begingroup$ Thanks for the comprehensive answer! It was really helpful. $\endgroup$
    – Tim Dumol
    Jul 9, 2012 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.