# 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

## 1 Answer

There are 9 such graphs.

First fix the isomorphism type of the underlying undirected graph. This can be a star, or a triangle and an isolated vertex, or a path.

Counting up to isomorphism, in the first case, there are 4 acylic orientations; in the second, just one, and in the third, again 4 orientations.

Also see number of directed acyclic graphs and a link there to count the number of acyclic orientations of a given undirected graph.