Prove that every tournament contains at least one Hamiltonian path.

Solution 1:

This can be proven using strong induction. Let $n$ be the number of vertices. When $n \le 2$, a hamiltonian path clearly exists. Now, for any given $n > 2$, pick any arbitrary vertex $v$. Partition all other vertices other than $v$ into the sets $V_{out}$ and $V_{in}$ -- $V_{out}$ contains all other vertices $u$ such that the edge $(v, u)$ exists, while $V_{in}$ contains all other vertices $u$ such that the edge $(u, v)$ exists.

Clearly $|V_{out}| < n$ and $|V_{in}| < n$, so by the inductive hypothesis, there is a hamiltonian path in both sets. Let $H_{out}$ be any hamiltonian path in $V_{out}$ and $H_{in}$ be any hamiltonian path in $V_{in}$. You can then form a hamiltonian path for all vertices by concatenating $H_{in}$, $v$, and $H_{out}$.

Solution 2:

A bit complicated for this problem, but the idea is often useful for other problems.

Let $V=\{v_1,v_2,\ldots,v_n\}$ be the set of vertices and $E$ be the set of edges of the graph $G$. Consider all permutations $v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)}$ (here $\pi\in S_n$) and for each one count the number of "left-right" arrows, i. e. denote $$ f(\pi):=|\{(i,j)\mid 1\leq i<j\leq n, \overrightarrow{v_iv_j}\in E\}|. $$ Now choose such a permutation $\pi$ for which the $f(\pi)$ is maximal. We claim that $v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)}$ is a desired Hamiltonian path. Indeed, if for some index $i\in\{1,2,\ldots,n-1\}$ we have $\overrightarrow{v_{\pi(i)}v_{\pi(i+1)}}\notin E$, then $\overrightarrow{v_{\pi(i+1)}v_{\pi(i)}}\in E$. Hence, if we "swap" $\pi(i)$ and $\pi(i+1)$ the value $f(\pi)$ will increase, which is impossible.

To be precise, consider another permutation $\pi'\in S_n$ defined as follows: $\pi(j)=\pi'(j)$ for $j\neq i, i+1$ and $\pi'(i)=\pi(i+1)$, $\pi'(i+1)=\pi(i)$. Now, note that $f(\pi')=f(\pi)+1>f(\pi)$.

Therefore, our tournament contains Hamiltonian path $v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)}$, as desired.