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 ? $$
Best Answer
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*}$$