3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Ah, I see. There can't be any directed cycle, since an edge can only go from a 'lower' vertex to a 'higher' vertex, and not the other way round. Thanks! By the way, which tool did you use to make those images? $\endgroup$ – user154185 Jul 11 '14 at 9:09
  • $\begingroup$ Indeed!! And I used tikz (a LaTeX package) for drawing the graphs. (By the way, there still might be some complications with infinite graphs, if they're included in the course.) $\endgroup$ – Rebecca J. Stones Jul 11 '14 at 9:10

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.