Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders262

a b

d c

king king

king not a king

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

.

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.

(a)Define a 10-chicken graph with a king chicken that has degree 1.

(b)Describe a 5-chicken 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.

Homework Problems

Problem 9.6. (a)Give an example of a digraph that has a closed walk including
two vertices but has no cycle including those vertices.

(b)Prove Lemma 9.5.2:
Lemma.The shortest positive length closed walk through a vertex is a cycle.

Problem 9.7.
Prove that the shortest odd-length closed walk through a vertex is an odd-length
cycle.

Problem 9.8.
LetRbe a binary relation on a setAandCnbe the composition ofRwith itselfn
times forn 0. SoC^0 WWDIdA, andCnC^1 WWDRıCn. RegardingRas a digraph,