2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy