Well, I am not sure about which algorithm you are talking about (there's no link and I could not find it at Wikipedia's tournamet page, nor Hamilton cycle page), but you can do something like this:
- Remove any vertex $v$ from $G$.
- In each strongly-connected component recursively calculate Hamilton cycles.
- If there are at least two SCCs, let $G_\top$ and $G_\bot$ be the top and bottom respectively; find vertices $u_\top \in G_\top$ and $u_\bot \in G_\bot$ such that $u_\bot \to v \to u_\top$ (we know that such vertices exist because $G$ was strongly connected).
- If there is exactly one SCC, find two vertices $u_\top, u_\bot \in G\setminus \{v\}$ such that
$u_\bot$ is a successor of $u_\top$ in the Hamilton cycle of $G \setminus \{v\}$ we previously found, and $u_\top \to v \to u_\bot$ (again, we know that such vertices exist because $G$ was strongly connected).
- Patch it all together.
This might take $O(n^3)$ time, but if you were to go backwards, i.e. constructing the graph, rather than deconstructing it, then SCCs calculation can be done on-line using find-union, and then it would take about $O(n^2\alpha(n))$ which is almost the same as a square.
I hope this helps $\ddot\smile$
Let's call your tournament $T$, and write $a \rightarrow b$ when there is an arc from $a$ to $b$. Write $a \rightarrow B$ when $B$ is a vertex set and $a$ has an arc to all members of $B$. Finally write $B \rightarrow a$ when all members of a set $B$ have an arc to $a$.
1) is straightforward enough. If $T$ has a cycle of length 3, then it can't be transitive by definition. Conversely, suppose $T$ is not transitive. Then $\forall a,b,c \in V(T) [a \rightarrow b, b \rightarrow c \Rightarrow a \rightarrow c]$ is false. What do you get by negating this expression ?
2) There's probably a better way for the tougher direction, but here goes. One way is to suppose $T$ has no Hamiltonian cycle and get that $T$ is not strongly connected. Let $C = c_1c_2 \ldots c_k c_1$ be a directed cycle of $T$ with the largest number of vertices.
Let $x \in V(T)$ such that $x \notin C$. If $c_i \rightarrow x$ for some $c_i \in C$, then $c_{i + 1} \rightarrow x$ as otherwise, $x \rightarrow c_{i+1}$ and $C' = c_1c_2 \ldots c_i x c_{i + 1} \ldots c_k c_1$ would be a bigger cycle (but $C$ is a largest cycle by assumption). Applying this reasoning inductively, we have that $C \rightarrow x$ when some $c_i \rightarrow x$.
So what do you get for any $x$ outside $C$ ? Either $C \rightarrow x$ or $x \rightarrow C$. Let $X = \{x : C \rightarrow x\}$ and $Y = \{y : y \rightarrow C\}$.
Take $x \in X, y \in Y$. If $x \rightarrow y$, then you can extend the $C$ cycle by deviating with $c_ixyc_{i + 1}$. So $y \rightarrow x$, for all $x \in X, y \in Y$. From this, you can deduce that there is no way to go from $x \in X$ to $c_i \in C$, hence $T$ is not strongly connected.
What's left for you to do is to argue that $C$ exists, and handle the cases when $X$ or $Y$ is empty (and tell us why both can't be empty).
Best Answer
Two things help us here:
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<j$, 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.