# Given an undirected connected graph, how many orientations would maintain acyclicity

Given an undirected connected simple graph $G=(V,E)$ there are $2^{|E|}$ orientations. How many of these orientations are acyclic?

-
If you have a cyclic graph, then the answer is simple because you can choose any orientation in which all edges are not pointed the same direction. If you have a graph where all cycles involve a disjoint set of edges, the answer is similarly simple. But if cycles share edges the answer is much more complicated. – user2566092 Apr 18 '14 at 20:58
@user2566092 Does it make any difference that $G$ is a simple graph? When cycles shared edges, are there any sufficient conditions with which the number of acyclic orientations is known ? (i.e., in/out degrees of the vertices) – seteropere Apr 18 '14 at 21:24

I came across a research paper from 1972 which addresses this question. Let $\chi(G, \lambda)$ be the chromatic polynomial. Then $(-1)^{V} \chi(G, -1)$ is the number of acyclic orientations of $G$, your graph. I let $V$ be the vertex count of $G$. This is Theorem 1.3 of the paper.
It's NP-Hard to compute the chromatic polynomial. That being said, for a small graph, you may be able to do it by eye-balling it. The term $\lambda$ represents the number of colors. There is another paper I found for computing the Chromatic Polynomial: whitman.edu/mathematics/SeniorProjectArchive/2009/fouts.pdf – ml0105 Apr 18 '14 at 21:09