Subscribe to the weekly news from TrueShelf

## Tournament Graphs

1. A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of vertices is connected by a single directed edge.

• Prove that every tournament graph has a hamiltonian path.

• Give an example of a class of tournament graphs on $n$ vertices having exactly one hamiltonian path.

2. Consider a tennis tournament where everyone plays everyone else and each match results in one player beating the other. Show that there is a player (say $X$) with the distinction that all other players were bested by $X$ in the following sense: given any other player (say $Y$), either $X$ beats $Y$ in their match, or there is another player (say $Z$), such that $X$ beats $Z$ and $Z$ beats $Y$.

Source: folklore

0

0

0

0

0

0

0

0

0
0