Mathematics for Computer Science

9.11. Summary of Relational Properties 351

in Figure 9.11, three of the four chickens are kings. Chickencis not a king in
this example since it does not peck chickenband it does not peck any chicken that
pecks chickenb. Chickenaisa king since it pecks chickend, who in turn pecks
chickensbandc.
In general, atournament digraphis a digraph with exactly one edge between
each pair of distinct vertices.

a b

d c

king king

king not a king

Figure 9.11 A 4-chicken tournament in which chickensa,b, anddare kings.

.

(a)Define a 10-chicken tournament graph with a king chicken that has outdegree

(b)Describe a 5-chicken tournament graph in which every player is a king.

(c)Prove
Theorem(King Chicken Theorem).The chicken with the largest outdegree in an
n-chicken tournament is a king.

The King Chicken Theorem means that if the player with the most victories is
defeated by another playerx, then at least he/she defeats some third player that
defeatsx. In this sense, the player with the most victories has some sort of bragging
rights over every other player. Unfortunately, as Figure 9.11 illustrates, there can
be many other players with such bragging rights, even some with fewer victories.

Problems for Section 9.5

Practice Problems

Problem 9.12.
What is the size of the longest chain that is guaranteed to exist in any partially
ordered set ofnelements? What about the largest antichain?