Assume $G$ is a tournament, i.e. a (finite) directed graph such that between any two vertices, $a$ and $b$, there is at least one edge in one of the two directions, $a\rightarrow b$ or $b\rightarrow a$.
- Show that there is at least one Hamiltonian path, i.e. a path, following the direction of the edges and visiting all vertices exactly once. (This part is a classical exercise and it is here to prepare for the second part of the problem).
- Consider all possible losers, i.e. the set of all vertices that can be end-points of Hamiltonian paths of the tournament, see Part (1). Show that the subgraph of all losers has a Hamiltonian cycle, i.e. a cycle that follows the direction of the edges and passes through every vertex exactly once and returns to the initial vertex.
For example
these are all tournaments and the $\color{red}{\text{red}}$ dots are the losers. Notice how there is always a cycle joining them.
Best Answer
This question was mostly answered in my answer to this other question. Instead of typing it all over again, I will quote from that answer. A digraph is strongly connected if there is a (directed) path from every vertex to every other vertex.
Proposition I. A tournament $T$ on $n$ vertices ($n\gt1$) has a Hamiltonian cycle if and only if it is strongly connected.
Proof of the nontrivial direction, quoted from my previous answer:
Suppose $T$ is strongly connected; we have to show that $T$ has a Hamiltonian cycle. We start by showing that $T$ has a cycle, not necessarily of length $n$. Choose a directed edge $uv$. Since $T$ is strongly connected, there is a path from $v$ to $u$; this path, together with the edge $uv$, gives us a cycle in $T$.
Let $C$ be a cycle in $T$ of maximum length $m$; we have to show that $m=n$. Let $W$ (for "winners") be the set of all players that beat at least one player in $C$, i.e., $v\in W$ iff there is a directed edge from $v$ to some vertex in $C$. Similarly, let $L$ (for "losers") be the set of all players beaten by at least one player in $C$, i.e., $v\in L$ iff there is a directed edge to $v$ from some vertex in $C$. We consider several cases.
Case 1. $W=\emptyset=L$.
In this case, the cycle $C$ contains all vertices of $T$; so $m=n$ and everything is fine. We shall see that each of the other cases leads to a contradiction.
Case 2. $W=\emptyset\ne L$.
Then $C$ has no "incoming" edges. If $u\in L$ and $v\in C$, then there is no path from $u$ to $v$, contradicting the assumption that $T$ is strongly connected.
Case 3. $W\ne\emptyset=L$.
If $u\in C$ and $v\in W$, then there is no path from $u$ to $v$, contradicting the assumption that $T$ is strongly connected.
Case 4. $W\cap L\ne\emptyset$.
If $v\in W\cap L$, then we can insert $v$ between two consecutive vertices of $C$ so as to obtain a cycle of length $m+1$, contradicting the assumed maximality of $m$.
Case 5. $W\ne\emptyset$, $L\ne\emptyset$, and $W\cap L=\emptyset$.
Since $T$ is strongly connected, there must be a directed edge $uv$ for some $u\in L$, $v\in W$. Then the vertices $u,v$ can be inserted in the cycle $C$ so as to obtain a cycle of length $m+2$, contradicting the assumed maximality of $m$.
Proposition II. Every tournament has a Hamiltonian path.
The easiest way to prove this is to consider a longest possible path in $T$ and show that, if it does not contain all the vertices, then we can construct a longer path. Another way (Rédei's theorem) is to use the in-and-out principle (aka inclusion-exclusion) to show that the number of Hamiltonian paths in $T$ is an odd number, therefore nonzero. Yet another way is to prove the Gallai-Milgram theorem which has Proposition II as a special case. A very silly way is to derive Proposition II from Proposition I about Hamiltonian cycles, which is what I will do.
Let $T$ be a tournament. It may or may not be strongly connected, but we can embed it in a strongly connected tournament $T'$ by adding two new vertices $u,v$, a directed edge $uv$, and directed edges $tu,vt$ for each $t\in T$. By Proposition I, $T'$ has a Hamiltonian cycle, which clearly has to contain the edge $uv$; deleting the vertices $u,v$ from the Hamiltonian cycle leaves us with a Hamiltonian path in $T$.
Proposition III. The subtournament on the set of all "losers" is strongly connected; hence it has a Hamiltonian cycle, provided there is more than one loser.
[Theorem 2 of my previous answer is essentially equivalent to this, but stated in terms of "winners" rather than "losers".]
Proof. Let $T$ be a tournament. Let $S$ be the set of all vertices $v\in T$ such that, for each vertex $u\in T$, there is a (directed) path from $u$ to $v$. (I will show that $S$ coincides with the set of all "losers" as defined in the question, i.e., the last vertex of some Hamiltonian path; this is just a simpler and more natural way to define them.)
Clearly, every loser belongs to $S$: if there is a Hamiltonian path ending at $v$, then we can get from any vertex to $v$ by following that path.
If $u\in S$ and $uv\in E(T)$ then $v\in S$. This is clear from the definition of $S$.
$S$ is strongly connected. To see this, consider any vertices $u,v\in S$. By the definition of $S$, there is a path from $u$ to $v$ in $T$; since there are no directed edges from $S$ to $T\setminus S$, the whole path must lie in $S$.
We finish the proof by showing that every vertex in $S$ is a loser; i.e., we consider a vertex $v\in S$ and find a Hamiltonian path which ends up at $v$. At any rate, by Proposition II there is a Hamiltonian path in $T$. Since there is no escape from $S$, the path must first traverse all the vertices (if any) in $T\setminus S$, then all the vertices in $S$. If $S=\{v\}$ we're done. Suppose $S$ contains more than one vertex. By Proposition I, we can find a Hamiltonian cycle in $S$; let $w$ be the successor of $v$ on that cycle. Follow the original Hamilton path as long as it stays in $T\setminus S$; then jump to $w$ and follow the cycle around to $v$. Q.E.D.