prove that number of acyclic orientations of a graph is the chromatic polynomial evaluated at -1. I have been trying to solve this problem for a while now. I am looking for a detailed proof. 
 A: There are two steps to the proof: proving that the number of acyclic orientations satisfies the deletion-contraction recurrence, and proving that (up to a factor of $(-1)^n$) it agrees with the chromatic polynomial evaluated at $-1$ on some base cases.
For the first step, given a pair of vertices $(u,v)$ with no edge between them in $G$, we want to compare acyclic orientations of $G$ to acyclic orientations of $G + uv$ and acyclic orientations of $G / uv.$ Their relationship is summarized in the following table:
\begin{array}{cccc}
  & G & G+uv & G /uv \\
\text{orientations with path $u \to v$} & \times 1 & \times 1 & \times 0 \\
\text{orientations with path $v \to u$} & \times 1 & \times 1 & \times 0 \\
\text{orientations with neither path} & \times 1 & \times 2 & \times 1
\end{array}
More precisely:


*

*There is a bijection between acyclic orientations of $G$ with a directed path $u \to v$, and acyclic orientations of $G + uv$ with a directed path $u \to v$  (not using the edge $uv$). 
An acyclic orientation of $G+uv$ with induces an acyclic orientation of $G$, which will keep a directed path if it has one. Conversely, an acyclic orientation of $G$ induces an acyclic orientation of $G+uv$, except for the choice of orientation of $uv$; but if a directed path $u\to v$ exists, that choice is forced, because the orientation $\overrightarrow{vu}$ would create a cycle.

*There is a bijection between acyclic orientations of $G$ with a directed path $v \to u$, and acyclic orientations of $G + uv$ with a directed path $v \to u$  (not using the edge $uv$). 
The proof is identical.

*There is a $1$-to-$2$ map between acyclic orientations of $G$ with no directed path between $u$ and $v$, and acyclic orientations of $G+uv$ with no directed path between $u$ and $v$ (not using the edge $uv$).
Here, any such orientation of $G$ can be extended in exactly two ways to an orientation of $G+uv$: we have complete freedom in how to orient $uv$, since we will not create a directed cycle. (And any acyclic orientation of $G+uv$ comes from an acyclic orientation of $G$.)

*There is a bijection between acyclic orientations of $G$ with no directed path between $u$ and $v$, and acyclic orientations of $G/uv$.
Given an acyclic orientation of $G/uv$, we can extend it to an acyclic orientation of $G$; give most edges the same orientation, and for any edge $uw$ or $vw$, give it the orientation of the edge between $(uv)$ and $w$ in $G/uv$. Going the other way, we only need to worry about what happens to vertices $w$ with both an edge $uv$ and $uw$, since these collapse to a single edge. But their orientations always agree, or else there would be a directed path $(u,w,v)$ or $(v,w,u)$.
So if $a(G)$ counts the acyclic orientations of $G$, we have $a(G) = a(G+uv) - a(G /uv)$ because this holds in each of the three rows of the table above.
Now it remains to check that if we evaluate the chromatic polynomial at $-1$, this gives $(-1)^n a(G)$ on some base cases. We could take empty graphs: these have chromatic polynomial $P(t) = t^n$, giving $P(-1) = (-1)^n = (-1)^n a(G)$, as desired. Complete graphs would also work. These have chromatic polynomial $P(t) = t(t-1)(t-2)\dotsb(t-n+1)$, so $P(-1) = (-1)^n n!$, matching $a(K_n) = n!$.
