§ Tournaments

[image at 49:00 from video math for comp sci lecture 10 ]

§ directed Hamiltonian path

A directed walk that visits every vertex exactly once.

§ Theorem: every tournament graph contains a directed hamiltonian path

Induction on the number of nodes. When we start thinking of the problem, we have both nodes and edges as parameters. But edges are directly related to nodes, so it makes sense we induct on nodes.

§ Induction

If n=1n=1 we are done. In the inductive step, assume it holds for n=nn=n. For n=n+1n=n+1, let's take out one node vv and see what happens. In the remaining graph, we still have a tournament graph on nn nodes. By the induction hypothesis we have a directed hamiltonian path v1v2…vnv_1 v_2 \dots v_n. We want to create a bigger path that includes vv.

§ Case 1

If v→v1v \rightarrow v_1 then we will get a path vv1…vnv v_1 \dots v_n.

§ Case 2

If v1→vv_1 \rightarrow v, then it is harder! Now what do we do? Ideally we want to plug vv somewhere in the sequence v1v2…vnv_1 v_2 \dots v_n. Let's consider the smallest ii such that v→viv \rightarrow v_i. We know that i≠1i \neq 1 as we are in case 2. 
v1 -> ...v[i-1] -> v[i] -> ... vn
                   ^
                   v
If we have v[i−1]→vv[i-1] \rightarrow v we are done because we get to insert vv into the path as v[i−1]→v→v[i]v[i-1] \rightarrow v \rightarrow v[i]. Because v[i]v[i] is the smallest index that vv beats, we must that v[i−1]v[i-1] beats vv --- otherwise ii is no longer the smallest index!

§ Chicken tournament

Either a chicken uu pecks a chicken vv then u→vu \rightarrow v or the other direction, v→uv \rightarrow u. We say that uu virtually pecks vv if there's a patch of pecking for uu to peck vv.
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 uu has highest out degree and is not the king. So there is some vertex vv such that u̸→v\not u \rightarrow v. Hence we have that v→uv \rightarrow u. In the other case, we have that u̸→w→⋆v\not u \rightarrow w \xrightarrow{\star} v.