Number of even spanning subgraphs

Pick a base vertex $v$. For any other vertex $w$, pick a path $P(v,w)$ from $v$ to $w$. $P(v,w)$ exists because $G$ is connected.

For a spanning subgraph $H\subseteq_{sp} G$, we speak of "flipping an edge $e$" to mean removing $e$ from $H$ if $e\in H$, and adding $e$ to $H$ if $e$ is not in $H$. This transformation yields another spanning subgraph. Note that flipping all edges along a path changes the degree of the end vertices of the path by one (provided the path is not a loop), but not any other vertices.

Define an equivalence relation $\sim$ on the set of all spanning subgraphs of $G$ as follows: $H_1\sim H_2$ if $H_2$ is obtained from $H_1$ by flipping all the edges along the path $P(v,w)$ for some $w$. Thus each equivalence class contains $2^{n-1}$ spanning subgraphs, as we have $n-1$ paths $P(v,w)$ to flip.

For any spanning subgraph $H$, there is a unique equivalent graph with even degree for all vertices $w\neq v$ (just flip all paths $P(v,w)$ for which $w$ has odd degree). Call this equivalent subgraph $H'$. In $H'$, $v$ must also have even degree, because the sum of degrees for all vertices is even (being equal to $2\times\text{number of edges}$), and the sum of degrees of all vertices $w\neq v$ is also even by hypothesis. Hence, each equivalence class has a unique even spanning subgraph.

There are $2^e$ spanning subgraphs, and thus $2^{e-n+1}$ equivalence classes, and thus $2^{e-n+1}$ even spanning subgraphs.

Let $v_1, \cdots, v_n$ be the vertices of the graph. Fixing the number of vertices, let us do induction on $e$, the number of edges.

Since $G$ is connected, The base case is $e = n-1$, which happens when $G$ is a tree. If $H \subseteq_{sp}G$ is even and contains at least one edge, then $H$ contains a cycle, but a tree can have no cycle, this is impossible. So the only even spanning subgraph is the trivial one, i.e., with $n$ vertices and no edges. So $|\{H\subseteq_{sp}G|H \mbox{ is even}\}| = 1$.

Suppose the assertion holds when $e = m \geq n-1$. Now suppose that $G$ is a connected graph with $m+1$ edges. Let $G'$ be a connected graph obtained by removing an edge $e_0 = v_1v_2$ from $G$. By induction hypothesis $|\{H\subseteq_{sp}G'|H \mbox{ is even}\}| = 2^{m-n+1}$.

How many even spanning subgraoh are there in $G$? There are $2^{m-n+1}$ of them which does not contain $e_0$, and $2^{m-n+1}$ of them containing $e_0$. To see this, let $v_1v_{a_1}v_{a_2}\cdots v_{a_{n-1}}v_2$ be a simple path (no repeated vertices) from $v_1$ to $v_2$. This must exists because $G'$ is connected. Let $\tilde H$ be a even spanning subgraph of $G$ with edges $e_0, v_1v_{a_1}, v_{a_1}v_{a_2}, \cdots, v_{a_{n-1}}v_2$. Then you can show that the following exhausts all even spanning subgraphs containing $e_0$:

$$ \{\tilde H \oplus H \ | \ H \subseteq_{sp} G', H \mbox{ is even} \}, $$

where $H_1 \oplus H_2$ means the "exclusive or" of $H_1$ and $H_2$, that is, the spanning subgraph whose edges are those which appears exactly once in $H_1$ and $H_2$.

This completes the sketch of the proof.