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

While trying to derive some formula, I encountered the following problem. Consider the set $C_n$ of all connected graphs on $n$ vertices. What is $$ \sum_{G \in C_n} (-1)^{|G|} ? $$ In other words, if we give a graph with an even number of edges a weight of $+1$, and a graph with an odd number of edges a weight of $-1$, what is the total weight of all connected graphs?

Here is an example: when $n=3$, any two edges form a connected graph, and the complete graph is also connected, so the value of the sum is $3 - 1 = 2$.

Surprisingly, the answer is $$ \sum_{G \in C_n} (-1)^{|G|} = (-1)^{n-1} (n-1)!. $$ This can be proved using the "exponential formula" (see e.g. the freely-available generatingfunctionology). The exponential generating function of all graphs, counted according to their parity, is $1+x$ (since for $n \geq 2$, the even and odd graphs cancel). Hence the exponential generating function for all connected graphs (counted according to their parity) is $$ \log (1+x) = \sum_{n \geq 1} (-1)^{n+1}\frac{x^n}{n} = \sum_{n \geq 1} (-1)^{n+1}(n-1)!\frac{x^n}{n!}. $$

My question is:

Is there an enumerative proof of the formula $$ \sum_{G \in C_n} (-1)^{|G|} = (-1)^{n-1} (n-1)! \quad ? $$

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.

I've independently rediscovered this formula while thinking about problem $B6$ from this year's Putnam competition $-$ I've managed to find this thread by googling "signed sums of connected graphs on signed vertices". I think my proof is different from the ones previously posted, though there is some similarity.

We prove by simple induction from $n-1$ to $n$. Let $H'_n \subset C_n$ be the set of all connected graphs $G$ in which the vertex $n$ is a leaf, i.e. has degree exactly 1. Then the graph $G' = G \setminus \{n\}$ obtained by deleting $n$ must be a connected graph on $1,\dots,n-1$, i.e. $G' \in C_{n-1}$. The mapping $G \mapsto G'$ is exactly $n-1$ to $1$: $G$ can be constructed from $G'$ in $n-1$ ways by adding one edge $(i,n)$ with $1 \le i \le n$. Finally, we clearly have $|G| = |G'| + 1$, so $(-1)^{|G|} = -(-1)^{|G'|}$. All together, we obtain $$\sum_{G \in H'_n} (-1)^{|G|} = (n-1)\sum_{G' \in C_{n-1}} -(-1)^{|G'|} = -(n-1)(-1)^{n-2}(n-2)! = (-1)^{n-1}(n-1)! $$

It remains to be seen that $\sum_{G \in C_n \setminus H'_n} (-1)^{|G|} = 0$, which we demonstrate by constructing a simple sign-changing involution: Suppose $G \in C_n \setminus H'_n$. Then the degree of the vertex $n$ is at least $2$ (of course it is not $0$, since $G$ is connected). Let $i,j$ be the two smallest neighbours of $n$ in $G$. Let $\sigma(G)$ be the graph obtained from $G$ by flipping the edge $(i,j)$. Clearly $|\sigma(G)| = |G| \pm 1$ has different parity, the neighbours of $n$ are unchanged so $\sigma$ is an involution, and the connectedness of the graph is independent of the existence of the edge $(i,j)$, since $i$ and $j$ are already connected via $n$. Thus the cancellation is proved.

I also remark that I rediscovered this formula while seeking a generalization of it: namely, if $C_{n,k}$ is the set of graphs on $n$ signed vertices with exactly $k$ connected components, then the corresponding sums over $C_{n,k}$ yield the signed Sterling numbers of the first kind: $$(*) \quad \sum_{G \in C_{n,k}} (-1)^{|G|} = s(n,k) = (-1)^{n-k} {n \brack k} $$

Indeed, the case $k=1$ is exactly the statement for $C_n$, and the general case can be obtained from it by considering the partition of $[n]$ into connected components $I_1, \dots, I_k$, and applying the formula for connected graphs on each $I_i$. The summation over all partitions then corresponds to counting the $n \brack k$ permutations with exactly $k$ cycles by first partitioning $[n]$ into the $k$ sets $I_1,\dots, I_k$, then choosing a cycle on each set. In both computations, the summand corresponding to the partition $I_1,\dots,I_k$ is $$\prod_i (-1)^{|I_i|-1}(|I_i|-1)! = (-1)^{n-k} \prod_{i} (|I_i|-1)!$$

More interestingly, it seems to me that $(*)$ follows directly by the argument in Yuval's answer, applied to $C_{n,k}$ and hierarchical forests with $k$ components. Perhaps all proofs here also yield a direct proof of $(*)$ - I have not checked.

Equation $(*)$ can also be shown directly using the definition of $s(n,k)$ by $$ (**) \quad x(x-1)\cdots(x-n+1) = \sum_{k=0}^n s(n,k) x^k $$ This proof is more directly related to the Putnam question (in fact, it is what lead me to $(*)$). Note that the left hand side of $(**)$ is the number of ordered $n$-tuples $(a_1,\dots,a_n)$ where $a_i \in [x]$ are pairwise distinct. A different way to count these is by using inclusion-exclusion on the sets $$A_{ij} = \{(a_1,\dots,a_n) \in [x]^n : a_i = a_j\}.$$ It is immediate to obtain, for a given graph $G$ on $[n]$, that $$|\bigcap_{(i,j)\in G} A_{ij}| = x^{c(G)},$$ where $c(G)$ is the number of connected components in $G$. Note that the inclusion-exclusion is performed by summation over such graphs $G$, with weights $(-1)^{|G|}$. Equation $(*)$ is then obtained by comparing the coefficients of $x^k$ in $(**)$.