Lemma: Invariant Pauli basis

The algebra $\mathfrak{F}(S)$ is spanned by Pauli monomials supported in $S$ whose $Z$-exponent satisfies

For connected $\Gamma$,

Proof. Conjugation by $G_v$ multiplies a Pauli monomial by $(-1{)}^{(\partial \beta {)}_v}$. Since Pauli monomials form a basis, the invariant subspace is exactly the stated span.

In the joint $X$-eigenbasis, a physical basis vector has eigenvalue $(-1{)}^{f_e}$ on link $e$, with $\partial f=0$. The incidence map of a connected graph has rank $|V|-1$ over ${\mathbb{Z}}_2$, so its kernel has dimension $|E|-|V|+1$.