Prove that any loop-less undirected graph admits an acyclic orientation.

Question

From answer below, I can just start at the smallest vertex and direct all the way up to the largest vertex. I didn’t realize it was as simple. So, for a tree, either I can mention trees don’t have cycles, or do the numbering method and arrive at same result? I think I don’t have to break it up into cases because 1 method will suffice for all.

Answer 1

Indeed, any such graph can be oriented as you need. Simply number the vertices and make all edges go from the lower numbered vertex to the higher number vertex, clearly no directed cycles will exist.

Answer 2

If this is the graph

then this is an acyclic orientation

because it has no directed cycles.

However, this orientation has a directed cycle, so it's not an acyclic orientation:

For graphs in general, we order the vertices in some way, and direct the edges in increasing order. To illustrate, here's a Erdos-Renyi(10,0.5) random graph:

Here, we can check that there are no directed cycles, and is thus an acyclic orientation.

To turn this into a formal argument, we number the vertices $\{1,\ldots,n\}$ via a function $f$, and weight each directed edge from $a$ to $b$ as $f(b)-f(a)$, then we observe: (a) summing the directed edge weights around a directed cycle gives $0$ (for each vertex $a$ in the cycle, we add $f(a)$ going into $a$, and subtract $f(a)$ coming out of $a$), and (b) observe that (in our chosen orientation, which only has edges from $a$ to $b$ if $a<b$) all directed edge weights are positive. So it's not possible to find a directed cycle.

(Alternatively, we can choose the maximum vertex (under the ordering) and observe it has no out-edges, so it's not part of a directed cycle. Delete it, then continue recursively, applying finite descent.)

Not all graphs will have a "cyclic orientation" (which I guess means orientations containing a directed cycle) as not all graphs have cycles, e.g.: