Topological Ordering and DAGs

1. Proof: Topological Order ⇒ DAG

Let's begin with the first implication: if a directed graph $G$ has a topological ordering, then it must be a DAG.

The most direct way to prove this is by contradiction. We will assume that a graph has a topological ordering and a cycle, and show that this leads to a logical impossibility.

Let's summarize the argument.

1. Assume the opposite: We assume a graph $G$ has both a topological ordering $L$ and a directed cycle.
2. Characterize the cycle: Let the cycle be represented by the sequence of vertices $v_1\to v_2\to \cdots \to v_k\to v_1$.
3. Apply the definition of topological ordering: According to the ordering $L$, for every edge $(u,v)$, $u$ must appear before $v$. Applying this to our cycle:
   • The edge $(v_1,v_2)$ implies $v_1$ comes before $v_2$ in $L$.
   • The edge $(v_2,v_3)$ implies $v_2$ comes before $v_3$ in $L$.
   • ...and so on, until...
   • The edge $(v_k,v_1)$ implies $v_k$ comes before $v_1$ in $L$.
4. Find the contradiction: If we chain these conditions together, we get that $v_1$ must come before $v_2$, which comes before ..., which comes before $v_k$, which in turn comes before $v_1$. This creates the absurd conclusion that $v_1$ must come before itself in the ordering.
5. Conclude: Since our initial assumption leads to a contradiction, it must be false. Therefore, a graph that has a topological ordering cannot have a cycle. In other words, it must be a DAG.

This half of the proof is quite intuitive. A topological ordering establishes a clear "before" and "after" for all connected vertices, while a cycle represents a "before and after itself" paradox.

2. Proof: DAG ⇒ Topological Order

Now for the second, more involved implication: if a graph $G$ is a DAG, then it must have a topological ordering.

To prove this, we need to show that we can always construct such an ordering for any given DAG. The proof hinges on a critical property that we touched upon in the last lesson: every non-empty DAG must have at least one vertex with an in-degree of 0. Such a vertex is often called a source.

Let's first prove this property, as it is the cornerstone of the main proof.

The logic of that proof is as follows:

• Assume for contradiction that a finite DAG has no source node, meaning every vertex has an in-degree of at least 1.
• Pick any vertex $v_1$. Since it has an incoming edge, we can walk backward to another vertex, $v_2$.
• Since $v_2$ also has an incoming edge, we can walk back to $v_3$, and so on.
• Since the graph has a finite number of vertices, this backward walk must eventually repeat a vertex. The portion of the path between the repeated vertices forms a cycle.
• This contradicts our initial premise that the graph is a DAG. Thus, our assumption must be false, and every DAG must have at least one source node.

With this lemma established, we can now prove the main statement using mathematical induction. This is a very common and powerful proof technique in computer science and is perfectly suited for this problem.

Let's unpack the inductive argument:

• Base Case: For a graph with $n=1$ vertex, a topological order trivially exists (it's just the single vertex).
• Inductive Hypothesis (IH): Assume that any DAG with $n-1$ vertices has a topological ordering.
• Inductive Step: We must show that a DAG $G$ with $n$ vertices also has a topological order.
  1. Using our lemma, we know that $G$ must have at least one source node $v$ (with in-degree 0).
  2. Let's create a new graph $G^{\prime }$ by removing $v$ and all of its outgoing edges from $G$.
  3. This new graph $G^{\prime }$ has $n-1$ vertices. Importantly, it is also a DAG, because removing vertices and edges can never create a cycle.
  4. According to our inductive hypothesis, since $G^{\prime }$ is a DAG with $n-1$ vertices, it must have a topological ordering. Let's call this ordering $L^{\prime }$.
  5. We can now construct a valid topological ordering for the original graph $G$ by simply placing $v$ at the beginning of $L^{\prime }$. The final ordering is $L=[v]+L^{\prime }$.
  6. Why is this valid? Because $v$ is a source node, it has no incoming edges, so placing it first violates no constraints. All of its outgoing edges point to vertices in $G^{\prime }$, which all appear after $v$ in our constructed list $L$. All constraints within $G^{\prime }$ are satisfied by $L^{\prime }$.

Since we can always perform this step, we have proven that any DAG must have a topological ordering.

3. An Alternative View: Cycles and Depth-First Search

Before we move on to implementation, there's another powerful way to think about the relationship between cycles and DAGs, which ties into an algorithm you're already familiar with: Depth-First Search.

When we run DFS on a directed graph, we can classify its edges. One special class is back edges: an edge from a vertex u to a vertex v that is an ancestor of u in the DFS tree. A key theorem in graph theory states:

A directed graph has a cycle if and only if a DFS traversal of it reveals a back edge.

This gives us a direct algorithmic tool: to check if a graph is a DAG, run DFS and see if you find any back edges. The following video provides an excellent proof of this theorem.

This connection between cycles and back edges is not just a theoretical curiosity. It forms the basis of the second major algorithm for topological sorting, which we will explore in a future lesson.

Conclusion

In this lesson, we have rigorously demonstrated the fundamental equivalence between a graph being acyclic and its capacity to be topologically sorted.

Key Takeaways:

• Proof (Topo Order ⇒ DAG): Proved by contradiction. The existence of a cycle would require a vertex to appear before itself in any linear ordering, which is impossible.
• Proof (DAG ⇒ Topo Order): Proved constructively via induction. The core insight is that every DAG has a source node (in-degree 0). By repeatedly finding a source, adding it to our list, and removing it from the graph, we can always construct a valid topological ordering.
• Algorithmic Insight: The property that a DAG must have a source node is not just a proof trick; it's the engine behind our first topological sort algorithm. The equivalence between cycles and DFS back edges is the engine behind the second.

We have now solidified the "why." In our next lesson, you will put this theory into practice. We will implement Kahn's algorithm, a BFS-based approach that is a direct translation of the constructive proof you studied today: it iteratively processes vertices with an in-degree of 0.