Friday, October 24, 2025

Cycle detection in certain digraphs

There is at least an edge between every pair of distinct vertices of a digraph $G$. Then $G$ is acyclic if and only if the indegrees of vertices of $G$ are all distinct.

===========================

Proof:





$(\Rightarrow)$ Arrange the vertices of $G$ from left to right by topological sort, such that there is not edge from right to left. Hence the $i$-th vertex from the left has indegree $i-1$ for $i\in[n(G)]$.


$(\Leftarrow)$ $G$ has a vertex $v$ of zero indegree, so $G$ cannot have a cycle containing $v$ and $G$ has edges from $v$ to all other vertices. Remove $v$ from $G$ and the remaining graph still has all-distinct indegrees. The statement clearly holds.

No comments: