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 ?$$

-
This is a really interesting question. Do you know of any other proofs besides the one that uses the exponential formula? – Mike Spivey Sep 30 '11 at 3:16
Proof by scientific induction. That's how I found the formula in the first place. – Yuval Filmus Sep 30 '11 at 7:26

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*}

-
Sorry for the extensive rewrite. There was some confusion between labeled partitions and graphs. Nice proof! – Yuval Filmus Sep 30 '11 at 13:10
A bijective interpretation appears in my own answer below. – Yuval Filmus Oct 1 '11 at 23:02

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.

-

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.

-
Here's another proof that the number of hierarchical trees with $n$ vertices is $(n-1)!$. Clearly, the number is the same if we replace "largest" with "smallest" in the definition. Then, we can create a hierarchical tree on $n$ vertices by attaching the new vertex $n$ to any one of the $n-1$ vertices in a hierarchical tree on $n-1$ vertices. Applied recursively, this gives us $|H_n|=(n-1)(n-2)\cdots(1)! = (n-1)!$. – Mike Spivey Sep 30 '11 at 14:37
Also, if you take a hierarchical tree on $n+1$ vertices, and you remove vertex $n+1$, you obtain a hierarchical forest on $n$ vertices. Your bijection at the end shows that the number of hierarchical forests on $n$ vertices with $k$ trees is the Stirling cycle number $\left[ n \atop k \right]$. – Mike Spivey Sep 30 '11 at 15:28