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 $u$ to $v$ means that player $u$ won against player $v$.

Exercise 28

Prove: Let $G$ be a tournament. If all vertices have the same out-degree, then $n$ is odd.

An interesting concept, closely related to Eulerian graphs, is called Hamiltonicity. A Hamiltonian path is a path from (a vertex) $s$ to (another vertex) $t$ that visits every vertex exactly once (since it is a path).

Theorem 11

Every tournament $G$ contains a Hamiltonian path.

The proof of this theorem will use the following simple fact: If we have a bit string $x= x[1]\ldots x[q]$, and we know that $x[0] =0$ and $x[q]=1$, then there must be some index $i$ such that $x[i]=0$ and $x[i+1]=1$. This fact can be proved by contradiction and is left as an exercise.

Proof (of Theorem 11):

Let $P = (v_1,v_2, \ldots, v_q)$ be the longest path in $G$. We argue that $P$ is a Hamiltonian path. Assume otherwise that some vertex $u$ is not on $P$. The idea is that, we know that, for every $i$, either $(v_i, u) \in E$ or $(u,v_i) \in E$. We know that $(v_1, u) \in E$ (otherwise, if $(u,v_1) \in E$, we get a path longer than $P$). Also, by the same reasoning, $(u,v_q) \in E$. For the rest of the edges, we do not know the directions between $v_i$ and $u$.

Now, defining the string $x[i]=0$ if $(v_i, u) \in E$ and $x[i] = 1$ otherwise. There must be some $i$ for which $x[i]=0$ and $x[i+1] = 1$, meaning that $(v_i,u) \in E$ and $(u,v_{i+1}) \in E$. We can then construct a path $P' = (v_1,\ldots, v_i, u, v_{i+1}, \ldots, v_q)$, contradicting the maximality of $P$.

Exercise 29

Present an algorithm that, given a tournament $G$ as input, efficiently computes a Hamiltonian path in $G$.

Another interesting property of a tournament is the existence of a king. Vertex $v$ is called a king in digraph $G$ if for every vertex $u \in V(G)$, there is a path of length at most two (edges) from $v$ to $u$¹.

Theorem 12

Every tournament contains a king.

Proof:

Let $v$ be a vertex in $G$, chosen to maximize the number of its out-neighbors, i.e., $v = \arg \max_{v \in V} \deg^+(v)$. We claim that vertex $v$ is a king. Denote by $V_1$ and $V_2$ vertices that are reachable from $v$ by a shortest path of length one or two respectively. Assume otherwise that $v$ is not a king. Then there must be a vertex $u \not \in V_1 \cup V_2$. Notice that $(u,v) \in E$ (otherwise, $u$ would have been in $V_1$, a contradiction) and $(u,w) \in E$ for all $w \in V_1$ (otherwise, $u \in V_2$, a contradiction). This implies that the out-neighbors of $u$ include $\{v\} \cup V_1$ and hence $\deg^+(u) > \deg^+(v)$, contradicting the fact that $v$ has largest out-degree.

Notice that, in the above proof, there is another potential choice of $v$, which is to choose $v$ to maximize the number of vertices reachable from $v$ by a path of length at most two. Since we know the validity of the above theorem, vertex $v$ must be a king. However, with this choice of $v$, it is unclear how to derive directly the fact that $v$ is a king (you can try to prove the above theorem with this choice of $v$ and you will see that you would get stuck).

Footnotes

1. We have no idea why they would call such a vertex a king 🙃 ↩