[Math] DAG proof by numbering nodes

graph theoryproof-writing

Prove that a directed graph is acyclic if and only if there is a way to number the nodes such that every edge goes from a lower number node to a higher numbered node.

I know this is true and that such an ordering is called a topological sort, but I'm having a hard time coming up with a formal proof. Any guidance would be much

Best Answer

Hint: We need to show two things:

  • (If part) If the graph has a topological sorting, then it is acyclic. Equivalently, it if the graph has a cycle (graph is not acyclic) then it does not have a topological sorting. How to show that? Let $G$ be a graph with a cycle $u_{1}, u_{2}, \dots, u_{1}$. Assume for the sake of contradiction that $G$ has a topological sorting, i.e., a sorting/labeling of the vertices with the properties that you mentioned. The vertices of the cycle in $G$ are also labeled. Show that they violate the properties of the topological sorting.

  • (Only if part) The graph is acyclic only if it has a topological sorting. Equivalently, if the graph is acyclic, then it has a topological sorting. Maybe just show how to make one? If a graph is acyclic, then it has some vertex $v$ that does not have any incoming edges...

Related Question