• Tournament graph: either $U$ beats $V$, so we have $U \rightarrow V$ or we have $V$ beats $U$ so we have the edges $V \rightarrow U$ for every $U, V$

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

• Example: A -> B -> D -> E -> C. Wait, C -> A. It's unclear how to talk about the best player!

§ 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=1$ we are done. In the inductive step, assume it holds for $n=n$. For $n=n+1$, let's take out one node $v$ and see what happens. In the remaining graph, we still have a tournament graph on $n$ nodes. By the induction hypothesis we have a directed hamiltonian path $v_1 v_2 \dots v_n$. We want to create a bigger path that includes $v$.

§ Case 1

If $v \rightarrow v_1$ then we will get a path $v v_1 \dots v_n$.

§ Case 2

If $v_1 \rightarrow v$, then it is harder! Now what do we do? Ideally we want to plug $v$ somewhere in the sequence $v_1 v_2 \dots v_n$. Let's consider the smallest $i$ such that $v \rightarrow v_i$. We know that $i \neq 1$ as we are in case 2.

v1 -> ...v[i-1] -> v[i] -> ... vn                   ^                   v

If we have $v[i-1] \rightarrow v$ we are done because we get to insert $v$ into the path as $v[i-1] \rightarrow v \rightarrow v[i]$. Because $v[i]$ is the smallest index that $v$ beats, we must that $v[i-1]$ beats $v$ --- otherwise $i$ is no longer the smallest index!

§ Chicken tournament

Either a chicken $u$ pecks a chicken $v$ then $u \rightarrow v$ or the other direction, $v \rightarrow u$. We say that $u$ virtually pecks $v$ if there's a patch of pecking for $u$ to peck $v$.

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 $u$ has highest out degree and is not the king. So there is some vertex $v$ such that $\not u \rightarrow v$. Hence we have that $v \rightarrow u$. In the other case, we have that $\not u \rightarrow w \xrightarrow{\star} v$.

• Reference: Math for computer science, lecture 10