Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)


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

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.