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

Related Content