How can I prove that a directed graph is acyclic if and only if the vertices can be sorted in such a way that the adjacency matrix has upper triangular form with only zeros in the diagonal?
I know that a graph is acyclic as long $A^n$ has zeroes along the diagonal for every $n \geq 1$. How can I prove the above statement?
Best Answer
If the graph is acyclic, then the topological sort algorithm produces the required ordering of vertices. Conversely, suppose the vertices can be sorted so all edges go from lower-numbered vertices to higher-numbered vertices; it's clear there cannot be a cycle.