When can I be sure a directed graph is acyclic?
- by Daniel Scocco
The definition for directed acyclic graph is this: "there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again."
So far so good, but I am trying to find some premises that will be simpler to test and that will also guarantee the graph is acyclic. I came up with those premises, but they are pretty basic so I am sure other people figured it out in the past (or they are incorrect). The problem is I couldn't find anything related on books/online, hence why I decided to post this question.
Premise 1: If all vertices of the graph have an incoming edge, then the graph can't be acyclic. Is this correct?
Premise 2: Assume the graph in question does have one vertex with no incoming edges. In this case, in order to have a cycle, at least one of the other vertices would need to have two or more incoming edges. Is this correct?