# When is the union of two acyclic subgraphs (of a digraph) still acyclic?

Let $D$ be some directed graph, and let $G$ and $G'$ be two acyclic subgraphs of $D$; let $E$ and $E'$ be their sets of edges. Is it possible to give a simple criterion on $E$ and $E'$ (sufficiency and necessity would be great, of course) for when the subgraph given by $E \cup E'$ is still acyclic?

(I can come up with [fairly trivial] necessary conditions, and also with [fairly elaborate] sufficient conditions, but all these are far from optimal.)

Thanks!

Edit: changed the wording and the title in response to Qiaochu Yuan's comments.

-
The union is always a DAG. – Qiaochu Yuan Feb 17 '12 at 5:45
@QiaochuYuan: If $V = V' = \{a, b\}, E = \{(a, b)\}, E' = \{(b, a)\}$, then $(V, E)$ and $(V', E')$ are both acyclic, but $(V\cup V' = V, E \cup E' = \{(a, b), (b, a)\})$ is not acyclic. – kjo Feb 17 '12 at 5:51
I suspect that no better criterion can be given than "$E\cup E'$ contains no cycles." Just out of curiosity, can I ask why you are interested in the union operation on DAGs? – Alex Kruckman Feb 17 '12 at 5:55
Oh, I didn't realize you weren't assuming that $V, V'$ are disjoint. I don't think it is good practice to call this operation the union of two DAGs. I would prefer that you call it the union of two sub-DAGs of some graph. (For me the union of two sets is either the disjoint union or it is only defined for subsets of a set. I don't like the union in the ZFC sense.) – Qiaochu Yuan Feb 17 '12 at 6:31
@AlexKruckman: I'm learning about posets, and I wanted to understand better when the transitive closure of the union of two partial orders on the same underlying set is still antisymmetric. This question, in turn, arises from a looking at the partial orders induced on a set $Y$ by a partial order on some other set $X$ and two functions $X\to Y$. – kjo Feb 17 '12 at 14:15