Graph conjecture. Is $|\sum(-2)^{F+C}|$, summed over spanning subgraphs, a power of two?

Question

While playing with some ideas in graph theory, I stumbled onto this conjecture:

If $G$ is a planar graph and $H$ is a spanning subgraph (a subgraph with the same vertex set), let $F_H$ be the number of faces of $H$, and let $C_H$ be the number of connected components of $H$. Then:

$$\sum_{\substack{H\subseteq G\\V(H)=V(G)}}(-2)^{F_H+C_H}=\pm2^k\text{ for some }k\in\Bbb N$$

In other words, if you every spanning subgraph contributes $(-2)^{F+C}$, and you add up all their contributions, the result is plus or minus a power of two.

(A topological intuition for the quantity $F+C$: $H$ is embedded in the plane. Thicken it a bit. Then the resulting set has $F+C$ boundary components.)

Is this true? I conjecture yes, but if so, how would we prove it? I tested it for a few graphs and it seems to hold up. I have an idea for a proof, but I'm not entirely sure of its correctness (or even how to put it into words). And can we predict $k$ from $G$?

And on a sidenote: does this generalize to nonplanar graphs? Clearly $F$ no longer makes sense, but Euler tells us that $V-E+F=C$, so we can ask about $\sum(-2)^{2C-V+E}$ instead.

Answer 1

The second formula (the one for general graphs) is, up to a factor of $(-2)^{C_G}$, the Tutte polynomial evaluated at $x=y=-1$, $T_G(-1,-1)$. This can be verified from Wikipedia's first definition of the polynomial.

The absolute value $|T_G(-1,-1)|$ counts the number of bicycles of a graph: spanning subgraphs that are both algebraic cycles (they include an even number of edges out of every vertex) and algebraic cocycles (a cocycle defined by some set of vertices $S$ is the set of all edges with exactly one endpoint in $S$). I don't have a good source for this claim, but here is the original citation for it, which I haven't yet read.

If we treat edge sets as vectors over $\mathbb F_2$, then the set of bicycles forms a vector space. To see this, we need to check that the set of bicycle is closed under addition of two vectors in $\mathbb F_2^{E(G)}$, which combinatorially corresponds to the symmetric difference of two edge sets. This:

• preserves the cycle property, because the symmetric difference of two even sets is even.
• preserves the cocycle property: the symmetric difference of the cocycle defined by $S$ and the cocycle defined by $T$ is the cocycle defined by the symmetric difference of $S$ and $T$.

Therefore addition in $\mathbb F_2^{E(G)}$ also preserves being a bicycle.

In particular, if this vector space is $d$-dimensional, then there are $2^d$ bicycles total, so $T_G(-1,1) = \pm 2^d$, and your formula gives $\pm 2^{C_G + d}$.