Let $G$ be a loop-less undirected graph. Prove that the edges of $G$ can be directed so that no directed cycle is formed.

1.2k Views Asked by At

Can someone please verify my proof or offer suggestions for improvement?

Let $G$ be a loop-less undirected graph. Prove that the edges of $G$ can be directed so that no directed cycle is formed.

Let us consider two cases. Suppose $G$ has no undirected cycles. Then, $G$ has no directed cycles (otherwise, the corresponding undirected graph would contain a cycle).

Now, suppose $G$ has an undirected cycle. Successively remove edges from $G$ to form a connected graph $G'$ without any undirected cycles. Now, $G'$ has no directed cycles, by the same reasoning as in the first case. Successively add directed edges to get the graph $G$ in the following manner: If edge $e = \{x,y\}$ is to be added, direct $e$ in such a way that no directed cycle is formed. Note that this can always be done at each step since there is either a directed path $\alpha$ from $x$ to $y$ or a directed path $\beta$ from $y$ to $x$ (but not both at the same time), or no such path at all ($\textit{this may need some explanation?}$). If this were not the case, then the union of $\alpha$ and $\beta$ would form a cycle.

Then, the (directed) graph $G$ has no cycles.

1

There are 1 best solutions below

2
On BEST ANSWER

Feedback on this approach:

  • $G$ is not assumed to be connected: so we need to work within connected components.

  • If edge $e = \{x,y\}$ is to be added, direct $e$ in such a way that no directed cycle is formed. We could encounter the situation depicted below, where orienting the orange dotted edge in either direction would not work.

    Problem

    You recognize this problem, but only say essentially "it can't arise", which is a proof by assertion. You offer no way to ensure that your algorithm avoids these situations. Actually, I don't think it's possible for an algorithm to ensure this: in the below figure, choosing either orientation of the orange dotted edge creates the above problem when choosing the orientations of the blue dotted edges later on.

    Problem 2

So, I have to conclude that this is not the right approach.

There is a very slick approach to this problem. I'll give you a hint, try drawing the graph with vertices $\{1,2,\ldots,n\}$ and an edge from $i$ to $j$ if $i<j$. Does it have any directed cycles?