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?
 A: 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.
A: 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.
