# Is it always possible to eliminate an edge from a DAG without introducing a cycle?

Given a DAG, is it always possible to find an edge such that if that edge is removed and the start and end nodes of the edge merged, the result is another DAG?

-

Yes!

In order to see this, consider a topological ordering $v_1,\ldots, v_n$ of the DAG and the arc $(v_1,v_i)$, where $v_i$, $2\leq i \leq n$, is the first node for which an arc starting from $v_1$ exists.

edit: note that you might end up with self-loops, i considered these cases to not be relevant.

-
If the original DAG is simple, you won't get self-loops (since the OP specified that the chosen edge is removed). – Ilmari Karonen Jan 15 '13 at 12:20
Depending on how exactly you define the contraction, you might end up with a non-simple graph in the process, even if the original graph is simple. Consider $D=(V,A)$ with $V={1,2,3}$ and $A={(1,2),(2,3),(1,3)}$. Contracting (1,2) will give you a non-simple graph and another contraction a self-loop. Of course, requiring that intermediate graphs also have to be simple by removing multiple occurences of the same arc will leave you free of self-loops – user58346 Jan 15 '13 at 13:06

As pm notes, if the DAG is finite (and has at least one edge), the answer is yes. To see this, note that the transitive closure of the edges of a DAG is a partial order on the nodes.

Pick any node $x$ which has at least one edge leading away from it, and consider the set $Y$ of nodes having an edge from $x$. As $Y$ is a finite subset of a partially ordered set, it has at least one minimal element $y$. Since $y$ is a minimal element of $Y$, it follows that there is no indirect path from $x$ to $y$, since any such path would have to pass through some other node $y' \in Y \setminus \{y\}$. Thus, removing the edge $(x,y)$ and merging $x$ and $y$ cannot introduce any cycles.

For infinite DAGs, this is not necessarily true. As a counterexample, consider the infinite DAG whose nodes are the rational numbers and there is an edge from $x$ to $y$ iff $x < y$. Then, for any two nodes $x < y$, there exists an indirect path from $x$ to $y$ via the node $(x+y) / 2$, and thus merging $x$ and $y$ would introduce a cycle.

-