[Math] Strongly Connected Tournament

graph theoryhamiltonicity

I need to prove that every strongly connected tournament is Hamiltonian. My professor suggested proving a stronger result(A strongly connected tournament on $n$ vertices contains cycles of length $3, 4, …, n$.

I am trying to prove by induction, but am stuck on concretely proving the base case even.

Best Answer

The base case holds. Take a king in the tournament. Because the graph is strongly connected, $|N^+(v)|,|N^-(v)| \neq \emptyset$. Therefore, both $|N^+(v)|$ and $|N^-(v)|$ have kings. Let the king of $|N^+(v)|$ be $k_+$. Clearly, it has to reach $v$ with a path of length $2$. Thus, we have a cycle of length three.

Now suppose that $G$ has a cycle $C$ of length $c$. There are two cases:

Easy case: There is some $v \in G -C$ s.t. $v$ loses to a $x \in C$ and beats a vertex $y \in C$. Then we splice $v$ into $C$ by $xvy$, creating a cycle of length $c+1$.

Hard case: Suppose that no such $v$ exists. Then we split the vertices of $G - C$ into two disjoint sets: $S$, set of vertices that only lose to vertices in $C$, and $P$, the set of vertices that only beat vertices in $C$. Neither of these sets can be nonempty, or the graph is not strongly connected.

There exists $s \in S$ and $p \in P$ s.t. $s$ beats $p$, otherwise the graph cannot be strongly connected.

Take the vertices $c_1, c_2,c_3 \in C$ s.t. $c_3$ follows $c_2$, which follows $c_1$ in $C$. By definition, $c_1$ beats $s$, $s$ beats $p$, and $p$ beats $c_3$. Splice $s$ and $p$ into $C$ by $c_1spc_3$. By skipping $c_2$, we create a cycle of length $c+1$.

Therefore, we have shown by induction that any strongly connected tournament contains cycles of all lengths $3,...,n$, and thus must contain a Hamiltonian cycle.

For more information, you can check out the paper where this result was first published.