I have the following problem: let $G$ be a finite directed graph with $V$ vertices $v\_i$ and $E$ (directed) edges $e\_j$. I know that if an edge $e\_k = (v\_i, v\_j)$ is in the graph, then the opposite edge $-e\_k = (v\_j, v\_i)$ is not in the graph. I also know that the graph contains at least one cycle. My goal is to render the graph acyclic by swapping the direction of some edges **pertaining to at least one cycle**.


I figured this was simple induction reasoning, i.e. swap an edge in any given cycle thus removing it, and repeat. But I cannot find a proof that it is possible to pick an edge which would not create a new cycle when swapped, nor can I find a counter-example with a finite graph.


The lemma I'd like to prove would be: given a graph $G$ such as above, there exists edge $(v\_i, v\_j)$ in one of the cycles so that replacing it with its opposite $(v\_j, v\_i)$ decreases the number of cycles in $G$ by at least 1. However, I couldn't find anything related... Any idea?


Thanks for your help



Removing cycles in a directed graph by swapping edges orientation
This is closely related to a standard (NP-complete) optimization problem, the minimum feedback edge set. Normally, this problem is defined as asking for the minimum set of edges $F$ to remove from a digraph $G$ to make $G-F$ acyclic. However, reversing the same set of edges $(G-F+F^R)$ also gives a DAG.


To see this, first note that each removed edge $f\_i$ must be part of a cycle $C\_i$ in $G-F+f\_i$, or else the set of removed edges would not be minimal. But then if there were a cycle in $G-F+F^R$, you could replace each edge $f\_i^R$ in this cycle by the corresponding path in $C\_i-f\_i$ and get a cycle in $G-F$.


The same argument works whenever $F$ is minimal, not just minimum. This might be helpful if you actually want to construct a set $F$, since it means you can do so without having to solve an NP-hard problem.


So this doesn't exactly give you a sequence of edges whose individual reversals decrease the number of cycles monotonically, but it does give you a set of edges that all participate in cycles and whose joint reversal eliminates all cycles.


