1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Orient each edge according to the levels given by a Breadth First Search. $\endgroup$ – logarithm May 6 at 1:56
  • $\begingroup$ NB – there are a few notions of graph in common use. This problem applies to graphs without self-loops. $\endgroup$ – Rylee Lyman May 6 at 2:03
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Same as @PkT 's answer. $\endgroup$ – Ethan Bolker May 6 at 2:05
  • $\begingroup$ @Ethan, yes, to a degree. But I like this formulation better since it doesn't need to depend on building the graph one node at a time. Others might prefer the other one for that exact same reason. $\endgroup$ – Henning Makholm May 6 at 2:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Same as @Mike 's answer. $\endgroup$ – Ethan Bolker May 6 at 2:05
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The problem is that if you don't do this systematically, then flipping edges to remove some cycles creates new cycles. And if you do do this systematically, you need to say how. $\endgroup$ – Misha Lavrov May 6 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.