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?
Best Answer
Yes, both of your premises describe necessary conditions for a cyclic graph. However, they only exclude trivial graphs from cycle analysis, and you'll want to use one of the standard algorithms to make sure a given graph is actually cycle-free.
There are actually fairly cheap algorithms for detecting cycles in graphs; if you are performing a topological sort on a graph, for example, you'll detect cycles during the sort. The exact choice of algorithm naturally depends on your graph (one outgoing edge or multiple?) and your requirements.