DAG proof by numbering nodes 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
 A: 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...
A: If $G$ is acyclic. We prove that there exist a vertex s.t. all edges are outer edges from it. Note  For the sake of contradiction let this not be satisfied. Let every node have an outer and inner edge. Let us start at some $x_1\in G$ and for each $i$ let $x_i$ be a node s.t. $x_{i-1}x_i$ is an edge in $G$ and was not previously chosen(if it exists). Due to our assumption this process will continue at least until we go back to some already chosen $x_m$ which will create a cycle. Contradiction. So some vertex has all outer edges. Label it $1$ and continue by induction.
If $G$ has a topological sorting if there is a cycle $x_1x_2....x_nx_1$ then since all $x_i-x_{i-1}$ are positive then $x_1-x_n<0$ contradiction.
