Unit 6: Directed Graphs, Tournaments, DAGs & Topological Sorting

1. Axiomatic Definition of a Directed Graph (Digraph)

A directed graph introduces orientation to relationships, reflecting asymmetry such as one-way roads, prerequisite structures, or state transitions.

Definition 6.1 (Directed Graph / Digraph): A directed graph (or digraph) $D = (V, E)$ consists of:

1. A non-empty set of vertices $V(D) = \{v_1, \dots, v_n\}$.
2. A set of directed edges (or arcs) $E(D) = \{e_1, \dots, e_m\}$, where each arc $e$ is an ordered pair of vertices:

Vertex $u$ is called the initial vertex (or tail), and $v$ is called the terminal vertex (or head). We say $e$ is directed from $u$ to $v$.

• A self-loop in a digraph is an arc of the form $(u, u)$.
• A simple digraph contains no self-loops and no duplicate directed edges $(u, v)$ with identical orientation.
• The underlying undirected graph of $D$, denoted $U(D)$, is obtained by replacing each directed arc $(u, v)$ with an undirected edge $\{u, v\}$ and consolidating multiple edges.

2. In-Degrees, Out-Degrees & The Digraph Handshaking Theorem

Definition 6.2 (In-Degree and Out-Degree): For any vertex $v \in V(D)$:

1. The out-degree $d^+(v)$ (or $\deg^+(v)$) is the number of arcs directed away from $v$:

1. The in-degree $d^-(v)$ (or $\deg^-(v)$) is the number of arcs directed into $v$:

1. The total degree of $v$ is $\deg(v) = d^+(v) + d^-(v)$.
2. A vertex with $d^-(v) = 0$ is called a source; a vertex with $d^+(v) = 0$ is called a sink.

Theorem 6.1 (The Directed Handshaking Theorem): In any directed graph $D = (V, E)$, the sum of the out-degrees equals the sum of the in-degrees, and both equal the total number of arcs:

Proof:

Every directed arc $e = (u, v) \in E$ has exactly one initial vertex $u$ and exactly one terminal vertex $v$. Therefore, each arc contributes exactly 1 to $\sum d^+(v)$ (at its tail) and exactly 1 to $\sum d^-(v)$ (at its head). Summing across all $m = |E|$ arcs proves the identity. $\blacksquare$

1. Hierarchy of Connectedness in Digraphs

Because edges in a digraph can only be traversed in the forward direction, connectivity is nuanced into three hierarchical levels:

Definition 6.3 (Connectedness Categories): Let $D = (V, E)$ be a digraph.

1. Weakly Connected: $D$ is weakly connected if its underlying undirected graph $U(D)$ is connected.
2. Unilaterally Connected: $D$ is unilaterally connected if for every pair of distinct vertices $u, v \in V$, there exists a directed path from $u$ to $v$ OR a directed path from $v$ to $u$.
3. Strongly Connected (Strong): $D$ is strongly connected if for every pair of distinct vertices $u, v \in V$, there exists a directed path from $u$ to $v$ AND a directed path from $v$ to $u$.

None of the reverse implications hold in general.

2. Strongly Connected Components (SCCs)

Definition 6.4 (SCC): A strongly connected component (SCC) of a digraph $D$ is a maximal strongly connected subgraph of $D$.

Theorem 6.2 (Strong Connectivity Equivalence Relation): The relation $u \approx v \iff (u \leadsto v \text{ and } v \leadsto u)$ is an equivalence relation on $V(D)$. The equivalence classes are the vertex sets of the strongly connected components.

The Condensation Digraph:

Shrinking each SCC into a single super-vertex yields the condensation of $D$, denoted $D^*$. The condensation $D^*$ is always a Directed Acyclic Graph (DAG).

1. Characterization of Eulerian Digraphs

Definition 6.5 (Eulerian Digraph): A directed graph $D$ is Eulerian if it contains a closed directed trail that traverses every directed arc of $D$ exactly once (a directed Euler circuit).

Theorem 6.3 (Eulerian Digraph Theorem): A weakly connected digraph $D$ is Eulerian if and only if it is balanced at every vertex:

Proof:

• $(\implies)$ In any directed Euler circuit, each entry into $v$ via an incoming arc must be paired with an immediate departure via an outgoing arc. Thus $d^+(v) = d^-(v)$.
• $(\impliedby)$ If $d^+(v) = d^-(v) \ge 1$ everywhere, start at any vertex $v_0$ and follow outgoing arcs. Since out-degree equals in-degree, we can never get stuck until returning to $v_0$, producing a directed cycle. Removing this cycle preserves balance. Splicing components together as in Theorem 2.2 produces an Euler circuit. $\blacksquare$

2. De Bruijn Sequences

A De Bruijn sequence $B(k, n)$ of order $n$ on an alphabet of size $k$ is a cyclic sequence of length $k^n$ in which every possible substring of length $n$ appears exactly once as a contiguous block! De Bruijn sequences are constructed as Eulerian circuits in the De Bruijn graph, where vertices are strings of length $n - 1$ and directed edges represent string overlaps of length $n$.

1. Definition of Tournaments

Definition 6.6 (Tournament): A tournament $T_n$ is an orientation of a complete graph $K_n$. That is, for every pair of distinct vertices $u, v \in V(T_n)$, there is exactly one directed arc between them: either $(u, v) \in E$ or $(v, u) \in E$, but not both. A tournament models a round-robin competition where every player plays every other player and ties are impossible.

2. Rédei's Theorem on Hamiltonian Paths

Theorem 6.4 (Rédei's Theorem, 1934): Every tournament contains a directed Hamiltonian path.

Complete Formal Proof (by induction on $n$):

• Base Case ($n = 1, 2$): $T_1$ is a single vertex. $T_2$ has one arc $(u, v)$, which is a path of length 1 visiting both vertices. Holds.
• Inductive Step: Assume every tournament on $n - 1$ vertices contains a directed Hamiltonian path.

Let $T$ be a tournament on $n$ vertices. Choose any vertex $v \in V(T)$, and consider the sub-tournament $T' = T - v$ on $n - 1$ vertices. By the induction hypothesis, $T'$ contains a directed Hamiltonian path:

Now consider the position of vertex $v$ relative to path $P$:

• Case 1: $(v, u_1) \in E(T)$.

Then $(v, u_1, u_2, \dots, u_{n-1})$ is a directed Hamiltonian path in $T$.

• Case 2: $(u_{n-1}, v) \in E(T)$.

Then $(u_1, u_2, \dots, u_{n-1}, v)$ is a directed Hamiltonian path in $T$.

• Case 3: Neither Case 1 nor Case 2 holds.

Then $(u_1, v) \in E(T)$ and $(v, u_{n-1}) \in E(T)$. As we travel along $P$ from $u_1$ to $u_{n-1}$, the arcs from the path vertices to $v$ start by pointing toward $v$ and end by pointing away from $v$. Therefore, there must exist an index $i \in \{1, 2, \dots, n - 2\}$ such that:

We can insert $v$ directly between $u_i$ and $u_{i+1}$ on the path:

This is a valid directed path visiting all $n$ vertices of $T$. Thus every tournament has a directed Hamiltonian path. $\blacksquare$

3. Landau's Theorem on Tournament Score Sequences

Definition 6.7 (Score Sequence): The score sequence of a tournament $T_n$ is the sequence of out-degrees sorted in non-decreasing order: $s = (s_1 \le s_2 \le \dots \le s_n)$.

Theorem 6.5 (Landau's Theorem, 1953): A non-decreasing sequence of non-negative integers $(s_1, s_2, \dots, s_n)$ is the score sequence of a tournament on $n$ vertices if and only if:

1. $\sum_{i=1}^k s_i \ge \binom{k}{2}$ for all $1 \le k \le n - 1$.
2. $\sum_{i=1}^n s_i = \binom{n}{2}$.

1. Directed Acyclic Graphs (DAGs)

Definition 6.8 (DAG): A Directed Acyclic Graph (DAG) is a directed graph containing no directed cycles.

DAGs model dependency networks, task scheduling, compilation order, and causal relationships.

Lemma 6.1 (Every Finite DAG Contains a Source and a Sink): Every finite DAG contains at least one vertex with in-degree 0 (a source) and at least one vertex with out-degree 0 (a sink).

Proof:

Pick any vertex $v_1 \in V$. If $d^+(v_1) = 0$, $v_1$ is a sink. Otherwise, choose an outgoing arc $(v_1, v_2)$. If $d^+(v_2) = 0$, $v_2$ is a sink. Repeat this process. Since the graph is finite and contains no directed cycles, we can never repeat a vertex. Thus the path must eventually terminate at some vertex $v_k$ with no outgoing arcs ($d^+(v_k) = 0$). Hence $v_k$ is a sink. A symmetric backwards search establishes the existence of a source. $\blacksquare$

2. Topological Sorting

Definition 6.9 (Topological Sort): A topological sort (or topological ordering) of a directed graph $D = (V, E)$ is a linear ordering of its vertices $v_{\pi(1)}, v_{\pi(2)}, \dots, v_{\pi(n)}$ such that for every directed arc $(u, v) \in E$, $u$ appears before $v$ in the ordering:

Theorem 6.6 (Topological Sort Existence Theorem): A directed graph $D$ admits a topological sort if and only if $D$ is a DAG.

Kahn's Algorithm for Topological Sort ($\mathcal{O}(|V| + |E|)$):

1. Compute the in-degree $d^-(v)$ for every vertex $v \in V$.
2. Initialize a queue $Q$ with all vertices having $d^-(v) = 0$ (all sources).
3. Initialize an empty list $L = []$.
4. While $Q$ is not empty:

• Dequeue a vertex $u$ from $Q$.
• Append $u$ to $L$.
• For each outgoing neighbor $v$ of $u$ (arc $(u, v) \in E$):
• Decrement $d^-(v) \leftarrow d^-(v) - 1$.
• If $d^-(v) == 0$, enqueue $v$ into $Q$.

1. If $|L| = |V|$, $L$ is a valid topological ordering!

If $|L| < |V|$, the graph contains a directed cycle (not a DAG).