# How many distinct directed acyclic graphs are there?

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one.

1. There is one where three periphery nodes point to a central node.
2. There is a central node pointing to three periphery nodes.
3. There are two variants of these two classes: one where two edges point out, and another where two edges point in.
4. There is a linear graph $A\to B\to C\to D$.

Is these 5 classes all? How to solve this problem for a general graph? Incorporating acyclic property seems tough.

• Haven't you missed $A \to B \leftarrow C \to D$? $A \leftarrow B \leftarrow C \to D$? – Stefan4024 Jun 21 '16 at 17:42
• And indeed $A\to B\to C\leftarrow D$ – almagest Jun 21 '16 at 18:29
• Are you not also missing a transitive triangle with an isolated vertex? – Shagnik Jun 22 '16 at 6:03