Graph Theory: A graph is acyclic then parent label is smaller than children label I've come across the following theorem in a couple of books but can't quite find a formal proof of it. 
Theorem: A directed graph is acyclic, if and only if it is possible to assign numbers to each of the vertices such that the parent vertex has a smaller number than all of it's children.
This makes intuitive sense since there aren't any cycles, I can label the higher vertices with smaller numbers than the lower vertices. But I'm not sure how to prove this formally.
 A: First show that a directed acyclic graph (DAG) must have a sink. (This is pretty straightforward: if there’s no sink, there must be a cycle (why?).) Now you can prove by induction on the number of vertices that every DAG can be numerically labelled so that each parent has a smaller label than each of its children: if it’s true for every DAG on $n$ vertices, let $G$ be a DAG on $n+1$ vertices, remove a sink $v$, label the resulting DAG $G-v$ suitably, and then give $v$ a label larger than any label in $G-v$.
For the other direction, suppose that $G$ is a directed graph whose vertices have been labelled with integers, and let $v_0,\ldots,v_m$ be a cycle in $G$. We can start the cycle anywhere, so without loss of generality assume that $v_0$ has the largest label of any of the vertices in the cycle; then $v_1$, which is a child of $v_0$, has label no larger than that that of $v_0$. Thus, $G$ has no satisfactory labelling.
A: Well, think carefully about what you mean by a vertex being "higher" than another. Clearly, a vertex that has no outgoing edges is the lowest. A vertex that only points to such vertices is only one step higher. On the other hand, if there is a vertex with a path to every other vertex, that is clearly as high as one could possibly get. To be explicit, here's a few ways to assign numbers to vertices that have this property:

Label a vertex $n$ if there is a path of length $n$ originating from the vertex, but no paths of length $(n+1)$.

This precisely captures the idea that "leaves" are the lowest level, things that only point to leaves are the next higher. Something which points to only leaves and things that point only to leaves are one step higher than that. We can extend this to use ordinal numbers for infinite graphs.
Another solution is:

Label a vertex $n$ if there are exactly $n$ vertices reachable from it.

Which works somewhat similarly.
I'll leave the proof that these actually work (and are well defined) to you.
