Appearance
Tournaments
One of the important classes of directed graphs is called tournaments. A tournament is an orientation of a complete graph. We can think of a tournament as the result of players participating in round-robin games where there is no tie or rematch. An edge directed from to means that player won against player .
Exercise 28
Prove: Let be a tournament. If all vertices have the same out-degree, then is odd.
An interesting concept, closely related to Eulerian graphs, is called Hamiltonicity. A Hamiltonian path is a path from (a vertex) to (another vertex) that visits every vertex exactly once (since it is a path).
Theorem 11
Every tournament contains a Hamiltonian path.
The proof of this theorem will use the following simple fact: If we have a bit string , and we know that and , then there must be some index such that and . This fact can be proved by contradiction and is left as an exercise.
Proof (of Theorem 11):
Let be the longest path in . We argue that is a Hamiltonian path. Assume otherwise that some vertex is not on . The idea is that, we know that, for every , either or . We know that (otherwise, if , we get a path longer than ). Also, by the same reasoning, . For the rest of the edges, we do not know the directions between and .
Now, defining the string if and otherwise. There must be some for which and , meaning that and . We can then construct a path , contradicting the maximality of .
Exercise 29
Present an algorithm that, given a tournament as input, efficiently computes a Hamiltonian path in .
Another interesting property of a tournament is the existence of a king. Vertex is called a king in digraph if for every vertex , there is a path of length at most two (edges) from to [1].
Theorem 12
Every tournament contains a king.
Proof:
Let be a vertex in , chosen to maximize the number of its out-neighbors, i.e., . We claim that vertex is a king. Denote by and vertices that are reachable from by a shortest path of length one or two respectively. Assume otherwise that is not a king. Then there must be a vertex . Notice that (otherwise, would have been in , a contradiction) and for all (otherwise, , a contradiction). This implies that the out-neighbors of include and hence , contradicting the fact that has largest out-degree.
Notice that, in the above proof, there is another potential choice of , which is to choose to maximize the number of vertices reachable from by a path of length at most two. Since we know the validity of the above theorem, vertex must be a king. However, with this choice of , it is unclear how to derive directly the fact that is a king (you can try to prove the above theorem with this choice of and you will see that you would get stuck).
Footnotes
We have no idea why they would call such a vertex a king 🙃 ↩︎