We were going over algorithms in class today to find a topological sort of a DAG (Directed Acyclic Graph), and our Professor mentioned that one could simply take a vertex with no in-degree, make it the first element in the sort, remove it and all associated edges, and repeat until the graph is empty. However, this seems to rely on the fact that any graph where each vertex has positive in-degree has a cycle. Is this true? I've been struggling with a proof for a bit, and was wondering if this claim was actually true.
[Math] Graph with Vertices with Positive In-Degree has a Cycle
graph theory
Best Answer
If the directed graph has a finite number of vertices then a path of maximum length must exist (because the length is at most the number of vertices).
So let $v_1,v_2,\dots , v_m$ be a sequence of maximum length.
A vertex $v_0$ must exist such that $v_0v_1$ is an edge.
We conclude that $v_0=v_k$ for some $k\in \{ 1,2,3\dots,m\}$. Otherwise $v_0,v_1,\dots, v_m$ would be an even longer path.
It follows that $v_k,v_1,\dots, v_k$ is a cycle in the directed graph.