Consider the directed acyclic graph (DAG) on V = {1, 2, 3, 4, 5, 6} shown…

Concept: A topological ordering of a directed acyclic graph is a linear arrangement in which every directed edge u → v places u before v. To test a proposed ordering, record each vertex’s position and check every edge; one reversed edge is enough to reject the ordering.

Application: The graph has the edges 1 → 2, 1 → 3, 2 → 4, 2 → 5, 3 → 4, 3 → 6, 4 → 5, and 4 → 6. Check each candidate against these precedence constraints:

1. For 1 2 3 4 5 6, every source vertex appears before its destination for all eight edges.

2. For 1 3 2 4 5 6, vertex 1 precedes 2 and 3; vertices 2 and 3 precede their destinations; and vertex 4 precedes 5 and 6.

3. For 1 3 2 4 6 5, swapping the relative positions of 5 and 6 causes no violation because the graph has no edge between 5 and 6; all eight listed edges still point forward.

4. For 3 2 4 1 6 5, vertex 1 occurs after both 2 and 3, so the edges 1 → 2 and 1 → 3 point backward in the sequence.

Cross-check: In every topological ordering of this graph, vertex 1 must precede both 2 and 3. The sequence 3 2 4 1 6 5 places 1 after both, independently confirming the violation.

Result: The sequence 3 2 4 1 6 5 is not a topological ordering.