[Math] How to correctly reason that this directed graph is acyclic

combinatoricscomputer sciencedirected graphsdiscrete mathematicsgraph theory

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

enter image description here

I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is equal to the ending vertex. But is this actually a reason you can say if someone asks you?

Is there maybe some kind of rule / formula where you can determine this by comparing the amount of vertices with the amount of edges?

We have here $6$ vertices and $10$ edges.

I hope you can give me some help because if someone asks me why this directed graph or generally a directed graph is acyclic, I would go like that here and I don't feel good about it.

Best Answer

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.

Related Question