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

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