as we are in case 2.
If we have we are done because we get to insert
into the path as . Because is the
smallest index that beats, we must that beats --- otherwise
is no longer the smallest index!
v1 -> ...v[i-1] -> v[i] -> ... vn
§ Chicken tournament
Either a chicken pecks a chicken then or the other
direction, . We say that virtually pecks if there's
a patch of pecking for to peck .
The chicken king is the chicken that virtually pecks all other chickens.
We can have multiple king chickens. We want to find at least one chicken king.
We may want to show that the vertex with the most number of outgoing edges
is going to be a king.
§ Theorem: chicken with highest out degree is the king
Proof by contradiction: assume has highest out degree and is not the king.
So there is some vertex such that . Hence we have
that . In the other case, we have that .