Prove that every tournament contains at least one Hamiltonian path.

Question

A tournament is a directed graph with exactly one edge between every pair of vertices. (So for each pair (u,v) of vertices, either the edge from u to v or from v to u exists, but not both.) You can think of the nodes as players in a tournament, where each player has to play against every other player. The edge points from the winner to the loser of a game. A Hamiltonian path (not cycle) is a sequence of consecutive directed edges that visits every vertex exactly once.

How can i prove that every tournament contains at least one Hamiltonian path? thanks your help!

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

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

Answer 3

Let T = (V,E) be a tournment.

Let P = $w_{1} w_2 \cdots w_{m}$ be a maximum lenght path starting with vertex $w_1$.

Let W = $\{ w_{1}, w_2, \cdots, w_{m} \}$ be the set of vertices of path P.

Suppose that $W \subset V$ (proper subset).

Then there exists $v \in V$ such that $v \notin W$.

Clearly any one of these pairs $(v,w_{1})$ and $(w_{m},v)$ cannot be edge of T, otherwise contradicts the maximum lenght.

Consider pair $(w_{m-1},v)$, if this pair is an edge of T, then $P_{m-1} = w_{1} w_2 \cdots, w_{m-1} v w_{m}$ is a path of greater length. A contradiction.

So the pair $(v,w_{m-1})$ is an edge of T.

Similarly the pair $(v,w_{m-2})$ is an edge of T. Otherwise $P_{m-2} = w_{1} w_2 \cdots, w_{m-2} v w_{m-1} w_{m}$ is a path of greater length. A contradiction.

Suppose $(v, w_{i})$ is an edge of T.

This implies that $(v,w_{i-1})$ is an edge of T. Otherwise $P_{i-1} = w_{1} w_2 \cdots w_{i-1} v w_{i} \cdots w_{m}$ is a path of greater length. A contradiction.

So by induction, $(v,w_{2})$ is an edge of T.

Then $P_{1} = w_{1} v w_{2} w_{3} \cdots w_{m-1} w_{m}$ is a path of greater length. A contradiction.

So every case is a contradiction.

Hence W = V.

This implies existence of Hamiltonian path in a Tournment T.

Answer 4

We prove this by induction on the number of vertices. If a tournament has just one vertex, the claim is true – the path containing just the single vertex is Hamiltonian. Now assume we know the claim is true for all tournaments on n vertices, and consider a tournament $G$ on $n + 1$ vertices. Let $v$ be any vertex in $G$. If we delete $v$ (and all edges with $v$ as an endpoint), the remaining tournament on n edges must have a Hamiltonian path by the inductive hypothesis. Label the vertices in this path $v_1, v_2, . . . v_n$. In the original tournament $G$, consider the possible orientations of the edges incident to $v$: There are three cases:

Case 1: If $vv_1$ is an edge (i.e. the edge containing $v$ and $v_1$ is oriented towards $v_1$), then there is a Hamiltonian path with vertex order $v, v_1, . . . , v_n.$

Illustration of Case 1

Case 2: If $v_nv$ is an edge, there is a Hamiltonian path with vertex order $v_1, . . . , v_n, v.$

enter image description here

Case 3: If Case 1 and Case 2 do not hold, as you look through the edges incident to v in order (starting with the edge containing v1, then the edge containing $v_2$, etc...) there must come a point where the edges switch from pointing towards v to pointing away from v. That is, there is at least one number $1 ≤ i ≤ n − 1$ for which $v_iv$ is an edge and $vv_{i+1}$ is an edge. Then there is a Hamiltonian path with vertex order $v_1, v_2, . . . , v_i, v, v_{i+1}, . . . , v_n$.

Illustration Case 3

Answer 5

Here is another proof for the problem.

For 2 vertices, we will always have a hamiltonian path.

Proof Idea:
In a graph with 2 vertices, we have a hamiltonian path.

1. We will take that path of 2 vertices.
2. Add another vertex to the graph(let's suppose it is 3). Now, as the tournament is complete, This newly added vertex will have an edge with each other vertex.
3. Take the last vertex from the hamiltonian path with 2 vertices. Suppose, this vertex is 2. If we add the direction from 2->3, we will immediately have a hamiltonian path. So, we will add the direction as 3->2.

4. Similarly, if the first vertex in 2 length of hamiltonian path is 1, Adding an edge 3->1 immediately creates a hamiltonian path of length 3. So, we will add 1->3.

   But this creates another hamiltonian path 1->3->2!
   

---

Now, We will take the 3 sized hamiltonian path from the tournament of 3 size which we just proved. Add a 4th vertex. We will do similar tasks as we just did for tournament size 2.
This time, the only difference is we have one mid vertex whose direction is not specified yet. We can see that whatever the direction is, it will always create a hamiltonian path. Because the direction of 'the newly added vertex and the first vertex' and the direction of 'the newly added vertex and the last vertex' will always be opposite.
So, we have a hamiltonian path for 4 vertices.

---

Construction for a general case:
Following this way, let's suppose we have a hamiltonian path for n vertices. What we will do is,

1. Take the n sized hamiltonian path, 1 to n.
2. Add a new vertex, n+1.
3. Add an edge between n+1 -> n.
4. Add an edge between 1 -> n+1. No path is detected yet.
5. Connect each of 2,3,...n-1 with n+1(We must because it is a tournament). But don't add direction.
6. As direction between 1->n+1 and n+1->n is opposite, when all the directions for 2,3,...n-1 to n+1 are added, three cases might appear.
   -All might be in upward direction. then, we have a hamiltonian path 1->2->3->...->n-1->n+1->n
   -All might be in downward direction. We have a hamiltonian path of 1->n+1->2->3->...->n
   -Arbitrary direction including atleast one upward and one downward direction. That will lead to an hamiltonian path.
   So, for any n, there will be atleast one hamiltonian path in a tournament.