Prove that every undirected graph has some orientation that is a Directed Acyclic Graph.
I understand that in graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. But I'm not sure how to prove it. Any help would be appreciated!
Best Answer
We give a simple algorithm that orients the edges of $G$ to get a DAG. Number the vertices $n$ vertices of $G$ arbitrarily $\{v_1,\ldots, v_n\}$. If $v_i$ and $v_j$ are adjacent in $G$, then direct the edge $v_iv_j$ as follows: If $i < j$ direct $v_iv_j$ towards $j$; otherwise direct the edge towards $i$.
The resulting orientation of the edges has no directed cycles. Indeed, for each $i$, every vertex reachable from $v_i$ is of the form $v_k; k > i$.