Kings in a Tournament

In a tournament, each pair of teams plays one game, which one of the teams wins and the other loses. The number of teams in a tournament can be any integer greater than one. In a particular tournament, team X is said to be a 'king' if, for every other team Y, X beats Y or a team that beats Y. The aim of this article will be to establish that every tournament contains at least one king, yet no tournament can have exactly 2 kings. In order to prove these facts, I will introduce some definitions from graph theory first, which are as follows:

An orientation $\vec{G}$ of a graph $G$ is an assignment of an orientation (direction) to each edge.

We call the directed edges arcs. So if the edge $vu$ is oriented from $v$ to $u$, we refer to the resulting directed edge as the arc $(v, u)$. We denote the arcs of $\vec{G}$ by $A(\vec{G})$. Sometimes, we may refer to $v$ as the tail of the arc and $u$ as the head of the arc.

The indegree $d^{-}(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the number of arcs that are oriented towards $v$, i.e. the number of arcs of the form $(u, v)$. Similarly, the outdegree $d^{+}(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the number of arcs that are oriented from $v$, i.e., the number of arcs of the form $(v, u)$.

The in-neighbourhood $S_I(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the set of all vertices $u$ such that $(u,v)$ is an arc in $\vec{G}$. Similarly, the out-neighbourhood $S_O(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the set of all vertices $w$ such that $(v,w)$ is an arc in $\vec{G}$.

In an oriented graph $\vec{G}$, a directed path is a path in which all the edges have the same orientation.

Any orientation of a complete graph is referred to as a tournament.
So, thinking of this to be a representation of an actual tournament where the arc $(v, u)$ indicates that $v$ beat $u$ in the competition, a vertex $v$ should be called a king if, for every other vertex $u$ in the graph, there is a directed path of length 1 or 2 from $v$ to $u$, since this implies that either $v$ beat $u$ or $v$ beat someone who beat $u$. Having thus restated our original problem in terms of graph theory, we are now ready to proceed with the proofs.

Tournament Graph with 5 Vertices having 4 Kings

Claim 1. Every tournament $T$ contains at least one king.

Proof. Suppose that $v$ is a vertex having maximum outdegree in the tournament graph $T$. Then, we claim that $v$ is a king in $T$. In order to verify this claim, it is enough to show that there is a directed path of length 2 from $v$ to each vertex in its in-neighborhood, denoted by $S_I(v)$.

So, let $u$ be any vertex belonging to $S_I(v)$. If there is a vertex $w$ in the out-neighbourhood of $v$, denoted by $S_O(v)$, such that $(w, u)$ is an arc of $T$, then the arcs $(v, w)$ and $(w, u)$ form a directed path of length 2 from $v$ to $u$.

On the other hand, if there is no such vertex in $S_O(v)$, then it must be the case that, for all vertices $y \in S_O(v)$, $(u, y)$ is an arc of $T$, which implies that $\forall y \in S_O(v)$, we have $y \in S_O(u)$. Now, since all the vertices in $S_O(v)$ also belong to $S_O(u)$, and additionally $v \in S_O(u)$, hence the outdegree of $u$ is greater than that of $v$. But this contradicts the choice of $v$ itself. Thus, there has to exist a vertex $w \in S_O(v)$ such that $(w, u)$ is an arc of $T$, and hence the claim is verified.


Claim 2. Let $q$ be a team that loses at least once in a tournament $T$. Then, the teams that beat $q$ include at least one king.

Proof. First, let us consider the case where $q$ is beaten by only one team $p$. In that case, $p$ is clearly a king in $T$ since it has a direct arc $(p, q)$ to $q$ and a directed path of length 2 to each of the remaining vertices of $T$, which all belong to the out-neighbourhood of $q$.

Now, if $q$ is beaten by more than one team, we simply consider the smaller tournament consisting only of the teams that beat $q$ and the games they play with each other. In other words, we will be looking at the tournament graph $T'$ induced on only the vertices belonging to the in-neighbourhood of $q$. From the previous claim, we know that the tournament $T'$ contains at least one king. Now, if $p$ is a king in the tournament $T'$, then $p$ must also be a king in $T$. This is true because, $p$ has a direct arc $(p, q)$ to $q$ and a directed path of length 2 to all the vertices in the out-neighbourhood of $q$, and being a king in $T'$, it is also guaranteed to have a directed path of length either 1 or 2 to each of the vertices (except itself) in the in-neighbourhood of $q$. Hence proved.


Claim 3. No tournament can have exactly 2 kings.

Proof. Let us assume, for the sake of argument, that a tournament has exactly 2 kings, say $q$ and $r$. As the two kings play each other, without loss of generality we can assume that $q$ beats $r$. However, since $r$ is a king in the tournament, $r$ must have beaten someone who beat $q$. In order for this to be possible, there must be at least one team who beat $q$ in the tournament. Now, from the previous claim, we know that there must be at least one king, say $p$, amongst the teams who beat $q$, and obviously, $p$ is different from both $q$ and $r$. Thus, our initial assumption is shown to be incorrect. Hence proved.