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.