# A little fun with tournaments (graphs).

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

1. 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).
2. 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.

• Shouldn't the first one with $4$ vertices have only one loser? – Vedran Šego Aug 2 '13 at 20:10
• Oh, indeed it should. – OR. Aug 2 '13 at 20:11
• For the first statement, check Wikipedia. The proof there is quite nice. – Vedran Šego Aug 2 '13 at 20:49
• Yes, I have solved both. I put it here for people's entertainment. – OR. Aug 2 '13 at 20:51
• Solving the problem is not necessarily a waste of time. And it could also be the next guy's question. – OR. Aug 2 '13 at 21:03

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.)

1. 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.

2. If $u\in S$ and $uv\in E(T)$ then $v\in S$. This is clear from the definition of $S$.

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

4. 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.