A software build system needs to compile modules where some depend on others. A developer tries to add a dependency so that module A requires B, B requires C, and C requires A. Why does this break the build system?
AThe system can't handle more than two levels of dependencies
BThe cycle creates an impossible ordering — A must be compiled before B, B before C, and C before A, which cannot all be satisfied simultaneously
CThe graph would have too many edges to traverse efficiently
DThe system only supports undirected dependency graphs
A DAG models dependencies precisely because its acyclicity guarantees a valid ordering exists. The moment you introduce a directed cycle, no topological ordering is possible — there is no linear sequence that puts every prerequisite before its dependent. Real dependency systems (package managers, build tools, course sequences) enforce acyclicity for exactly this reason: a cycle represents an incoherent circular requirement.
Question 2 Multiple Choice
Which property is guaranteed in every directed acyclic graph?
AEvery vertex has exactly one outgoing edge
BEvery vertex is reachable from every other vertex
CThere exists at least one vertex with no incoming edges (a source)
DThe graph has exactly one connected component
Every DAG must have at least one source (a vertex with no incoming edges). The proof is by contradiction: if every vertex had at least one incoming edge, you could always follow edges backward indefinitely, eventually revisiting a vertex — forming a cycle, which contradicts the DAG property. The symmetric argument proves every DAG also has at least one sink (vertex with no outgoing edges).
Question 3 True / False
A directed graph has a topological ordering if and only if it is a DAG.
TTrue
FFalse
Answer: True
This is the fundamental equivalence: the existence of a topological ordering is exactly equivalent to acyclicity. If a directed graph contains a cycle, no linear ordering can place every vertex before those it points to — some edge will always go 'backward.' Conversely, if there are no cycles, a DFS-based algorithm can produce a topological ordering by reading finish times in reverse. A DFS cycle check and a topological sort are essentially the same computation.
Question 4 True / False
A DAG can contain directed cycles, as long as those cycles don't include most vertex in the graph.
TTrue
FFalse
Answer: False
By definition, a DAG contains NO directed cycles — not even partial ones. Even a single cycle involving just two or three vertices violates the acyclic property and destroys the guarantee of topological ordering. The name 'directed acyclic graph' means the entire graph is cycle-free, not just that cycles are limited in scope.
Question 5 Short Answer
Why does every DAG have at least one source (a vertex with no incoming edges)? Explain using a proof by contradiction.
Think about your answer, then reveal below.
Model answer: Assume every vertex in the DAG has at least one incoming edge. Then starting at any vertex, you can always follow an edge backward to a predecessor. Since the graph is finite, you must eventually revisit a vertex — creating a directed cycle. But that contradicts the assumption that the graph is acyclic. Therefore, our assumption was false: at least one vertex must have no incoming edges.
This argument is important not just for DAGs but as a template for structural reasoning about directed graphs. The same logic shows every DAG has at least one sink: if every vertex had an outgoing edge, following edges forward would eventually create a cycle. Sources and sinks are the 'endpoints' that every DAG must have, and they are where topological orderings begin and end.