Cycles in Graphs

A cycle in a directed graph $G$ is a path $v_{0}, \dots, v_{k} (k \geq 1)$ such that $(v_{k}, v_{0})$ is also an edge.
We call $G$ cyclic if it has a cycle, otherwise acyclic.

CYCLICITY

Given: A directed graph $G = (V, E)$
Return: YES if $G$ is cyclic, NO otherwise

Topological Sort solves CYCLICITY in linear time

Lemma: Let $G$ be a directed graph. If $G$ has no cycles, then there is some vertex with zero in-degree.

Proof: Let there be a vertex $v_{0}$ , this must have a vertex pointing to it since it has a non-zero in-degree. $$v_j \rightarrow \ldots v_i \rightarrow \ldots \rightarrow v_0$$ since the graph is finite at some point, $v_{j} = v_{i}$ thus creating a cycle $◻$ .