Graph Theory In any flock every pair of chickens will engage

Graph Theory:

In any flock, every pair of chickens will engage in barnyard squabble to determine which of the two is dominant over the other; hence the origin of the phrase pecking order. In general, pecking is not transitive, meaning that if C₁ pecks C₂, who pecks C₃, then it is not necessarily the case that C₁ pecks C₃. We will say that in a given flock with an established pecking order, chicken K is a king if, given any other chicken C, either K pecks C directly or there exists a field marshall F such that K pecks F, who pecks C.

Prove that any flock of chickens with an established pecking order has a king.

Solution

Let us say chicken K has the maximum pecking count. If another chicken K\' has the same number of peck count, then by transitivity, K\' will have to peck all the chicken which were pecked by K, this contradicts the fact that K has pecked most number of chickens. Therefore, it is only possible if K has pecked everyone including K\'. Therefore, K is the king of the flock. Therefore, any flock of chickens with given pecking order has at least one King!