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!
On
Any undirected graph can be made in to finite number of directed graphs, Now there are two cases, none of these directed graphs have a cycle (A) and you have at least one (B). So if it is case (A) we have at least one Directed Acyclic Graph. For Case(B), Take all cases with the cycle, and flip the direction of one of the edge to make it a Directed Acyclic graph or all cycles can be removed by flipping an edge.
Im not a math guy. so just an idea
On
Add vertices $\{v_1, \cdots, v_n\}$ to the directed graph one by one. When vertex $v_i$ is added, assign all edges between $v_i$ and $\{v_1, \cdots, v_{i-1}\}$ to be outgoing from $v_i$.
Once the process is done, $v_n$ is not in a directed cycle. So we can remove $v_n$ and its associated edges. Now $v_{n-1}$ cannot be in any cycles, and so on. This means that we came up with an acyclic directed version of our graph.
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$.