reciprocity formula for f_G

Statement

Let $G$ be a simple graph, and $\bar{G}$ is its complement, $f_{G}$ is the function f_G (graph). Then,

f_{\bar{G}} (x) = (- 1)^{n - 1} f_{G} (- x - n)

where $n$ is the number of vertices of $G$

Proof

Similar to that of Cayley's formula#Proof 1 induction. We define the more general function

F_{G} (x, x_{1}, \dots, x_{n}) = \sum_{T spans G^{+}} x^{\deg_{T} (0) - 1} \prod_{i = 1}^{n} x_{i}^{\deg_{T} (i) - 1}

We shall show via inducting on the number of vertices that

F_{\bar{G}} (x, x_{1}, \dots, x_{n}) = (- 1)^{n - 1} F_{G} (- x - n, x_{1}, \dots, x_{n})

One can show that this is true when $x_{i} = 0$ , which kills everything except the trees such that vertex $i$ is a leaf. We may then remove it and apply the inductive hypothesis.

Furthermore, the degree of both sides are less than $n - 1$ , and so we may conclude via this lemma that the difference is identically 0.