How do you correctly reason that this directed graph is acyclic?

A more general approach to this is given by topological sorting. In particular, a topological sort exists if and only if the graph is a directed acyclic graph. The 'algorithms' described in the other answers effectively perform a topological sort, in that they repeatedly remove vertices with no incoming/outgoing edges.

For instance, a topological ordering of your graph is given by $A,B,C,D,E,F$ and if you redraw the graph so that the earlier vertices are higher than later vertices (not necessarily linearly) you can see that there are no 'upward' edges, so there can be no cycle.


Step 1. Since $A$ has no indegree it can't be part of any cycle. So remove it. We have now graph $G_1$.

Step 2. Since $C$ has no indegree it can't be part of any cycle (in this new graph $G_1$). So remove it. We get $G_2$

Step 3. Now in $G_2$ nodes $B$ and $D$ have no indegree so remove them.


A directed cycle can't involve $F$ since no arrows start from $F$. So you can delete $F$ and all arrows that land at $F$ from the graph. The original graph is acyclic if and only if the new graph is.

Repeat the procedure with $E$ now. Then with $D$, then with $B$ and $C$.

In the end, only $A$ remains, with no edges, that is an acyclic graph.