12
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Perhaps you can start at an arbitrary node and traverse a path until you cannot go anymore. If your path exhausted all nodes, you have found a Hamiltonian path. Else, there must be a node you have not used yet that points in to the current node you stopped at. Then show you can always augment your path by adding one new node. Keep augmenting until you are done. $\endgroup$ – Michael Mar 4 '16 at 4:54
17
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ This (nice) argument works perfectly fine with $n = 0$ (not $n \leq 2$) as the induction base. Of course, one of the sets $V_{out}$ and $V_{in}$ can be empty for small $n$, but this can just as well happen for large $n$, so extending the induction base to $n \leq 2$ doesn't help. (Fortunately, the case when one of $V_{out}$ and $V_{in}$ is empty is easy to handle: just let $H_{in}$, resp. $H_{out}$, be an empty list of vertices.) $\endgroup$ – darij grinberg Feb 6 '17 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.