Number of connected graphs on labeled vertices, counted according to parity

Here’s a proof by induction.

Let $w(n) = \sum\limits_{G\in C_n}(-1)^{e(G)}$, where $e(G)$ is the number of edges in $G$. I will assume that the vertex set of $G\in C_n$ is $[n] = [1,n]\cap\mathbb{Z}^+$. Suppose that $w(k) = (-1)^{k-1}(k-1)!$ for $1\le k \le n$.

Let $H$ be a labeled partition of $[n]$. Suppose that $H$ has components (parts) $H_1,\dots,H_k$. Denote $v_i = |H_i|$. Let $P(H)$ be the set of permutations whose cycles are exactly $H_1,\dots,H_k$ (in any internal order). Clearly $$\vert P(H)\vert = \prod_{i=1}^k(v_i-1)!,$$ and if $G_n$ is the set of all labeled partitions of $[n]$, $$\sum_{H\in G_n}\vert P(H)\vert = n!.$$

Let $C_{n+1}(H)$ be the set of $G\in C_{n+1}$ that decompose into connected components $H$ after deleting vertex $n+1$. Consider a component $H_i$ of $H$. If $G\in C_{n+1}(H)$, vertex $n+1$ must be adjacent in $G$ to at least one vertex of $H_i$. For $j=1,\dots,v_i$ there are $\dbinom{v_i}{j}$ ways to attach vertex $n+1$ to $j$ vertices of $H_i$. It follows that $$\begin{align*} \sum_{G\in C_{n+1}(H)}(-1)^{e(G)} &= \prod_{i=1}^k\sum_{j=1}^{v_i}\binom{v_i}{j}(-1)^jw(v_i)\\ &= \prod_{i=1}^k(-1)^{v_i-1}(v_i-1)!\sum_{j=1}^{v_i}\binom{v_i}{j}(-1)^j\\ &= \prod_{i=1}^k(-1)^{v_i-1}(v_i-1)!(-1)\\ &= \prod_{i=1}^k(-1)^{v_i}(v_i-1)!\\ &= (-1)^n\prod_{i=1}^k(v_i-1)!\\ &= (-1)^n\vert P(H)\vert \end{align*}$$

and hence that

$$\begin{align*} w(n+1) &= \sum_{H\in G_n}\quad\sum_{G\in C_{n+1}(H)}(-1)^{e(G)}\\ &= \sum_{H\in G_n}(-1)^n \vert P(H)\vert\\ &= (-1)^n\sum_{H\in G_n}\vert P(H)\vert\\ &= (-1)^n n!. \end{align*}$$

Here's a different take on Brian's proof.

Let $H_n$ be the set of all rooted trees on $[n]$ such that the root of each subtree is the largest vertex in the tree. We call such trees hierarchical.

We construct a sign-changing involution $\sigma$ on $G_n \setminus H_n$, where $G_n$ is the set of all connected graphs on $n$ vertices. Take a graph $G \in G_n$. Removing vertex $n$ splits the graph into connected components $C_1,\ldots,C_m$.

Suppose first that there is some component $C_i$ such that $n$ is not connected only to $\max C_i$; let $C_i$ be the first such component. The involution $\sigma$ is defined by complementing the edge $(n,\max C_i)$.

Suppose now that for all components it is true that $n$ is connected only to $\max C_i$. Let $C_i$ be the first component which is not hierarchical. The involution $\sigma$ is defined by applying $\sigma$ recursively on $C_i$.

The existence of $\sigma$ shows that the sum in question is equal to $(-1)^{n-1}$ times the number of hierarchical trees on $n$ vertices (here $n-1$ is the number of edges in such a tree). We claim that this number is $(n-1)!$.

Proof 1 (Y.F.): We present a bijection between $H_n$ and the set of all permutations in $S_n$ starting with $n$.

The coding $c$ of trees is defined as follows. The code of a hierarchical tree $T \in H_n$ with subtrees $T_1,\ldots,T_m$ is $$c(T) = nc(T_1)\cdots c(T_m).$$ In other words, $c$ consists of the vertices in prefix order.

To decode a permutation, use the following algorithm. The permutation must start with $n$. Suppose the next symbol is $t_1$. The substring commencing at $t_1$ and terminating just before the first symbol $t_2$ larger than $t_1$ codes the first subtree, which is decoded recursively. The rest of the subtrees are decoded analogously.

Comment (Mike Spivey): The proof shows that the number of hierarchical forests with $k$ trees on $n$ vertices is equal to $\left[ n \atop k \right]$, a Stirling number of the first kind.

Proof 2 (Mike Spivey): All hierarchical trees on $n$ vertices can be constructed as follows. Start with the vertex $n$. Connect vertex $n-1$ to one of the existing vertices ($1$ possibility). Connect vertex $n-2$ to one of the existing vertices ($2$ possibilities). And so on. At the end, vertex $1$ can be connected to any of the $n-1$ preceding vertices. So in total, there are $(n-1)!$ hierarchical trees.

Let me sketch a standard combinatorial proof. Denote by $f_n(t)$ the inversion polynomial, defined as the summation over all spanning trees $\tau \subset K_n$ of $t^{inv(\tau)}$. It is well known that $f_n(t)=T_{K_n}(1,t)$ the Tutte polynomial of a complete graph. This can be proved using recurrence relations (many possibilities) or bijectively (see this paper by Gessel and Wang). Therefore, $f_n(1+t)=T_{K_n}(1,1+t) = \sum_G t^{|G|}$ by definition of the Tutte polynomial, and $f_n(0)=\sum_G (-1)^{|G|}$ is the desired summation in the problem. By definition of tree inversions, the only trees with no inversions are increasing trees. There are exactly $(n-1)!$ of them. By induction: new leaf $n$ has $n-1$ places it can be attached to. For the definition of the inversion polynomial, connections to Tutte polynomial, and recurrence relations, see here and there.

P.S. Just noticed - increasing trees are called hierarchical trees in the previous answer.