### DAG Warm-Up Problem

```DAG Warm-Up Problem
McNally and fellow guard Brandyn Curry, who combined for 26
second-half points, came up big for Harvard throughout the
final frame. After going scoreless in the first half, Curry scored
12 straight points for the Crimson off four three-pointers
during a stretch of 3:27, turning a one-point deficit into a
Indegree and outdegree of a vertex
in a digraph
• Vertex v has outdegree 3
• Vertex has indegree 2
v
• Lemma. Any finite DAG has at least one
node of indegree 0.
• Proof. In-class exercise.
Tournament Graph
• A digraph is a tournament graph iff every
pair of distinct nodes is connected by an
edge in exactly one direction.
• Theorem: A tournament graph determines
a unique ranking iff it is a DAG.
H
P
H
Y
D
P
Y
D
Tournament Graphs and Rankings
• Theorem: A tournament graph determines
a unique ranking iff it is a DAG.
• What does this mean?
Tournament Graphs and Rankings
• Theorem: A tournament graph determines
a unique ranking iff it is a DAG.
• What does this mean?
• That there is a unique sequence of the
nodes, v1, …, vn, such that V = {v1, … vn}
and for any i and j, i<j implies vi→vj.
If a tournament graph G is a DAG, then
G determines a unique ranking
Proof by induction on |V|. The base case |V|=1 is trivial.
Induction. Suppose |V|=n+1 and every tournament DAG
with ≤n vertices determines a unique ranking.
G has a unique vertex v of indegree 0. (Why is there a
vertex of indegree 0? Why is it unique?)
Let S be the set of all vertices w such that there is an
edge v→w. (What vertices in V are actually in S?)
The edges between nodes in S comprise a tournament
DAG (why?) and hence determine a unique ranking v1,
… vn.
Then v, v1, … vn is a unique ranking for the vertices of G.
Vertex v can only go at the beginning of the list since
v→vi for i = 1, … n (why?).
If a tournament graph G determines a
unique ranking, then G is a DAG
• Proof: Exercise
```