Number of even spanning subgraphs An even graph is a graph all of whose vertices have even degree. 
A spanning subgraph $H$ of $G$, denoted by $H \subseteq_{sp} G$, is a graph obtained by $G$ by deleting only edges of $G$.
I want to show that if $G$ is a connected graph, then
$\big|\{H \subseteq_{sp} G | H$ $is$ $even\}\big| = 2^{e-n+1}$, where $e$ is the number of edges and $n$ the number of vertices of $G$.
Can anyone give me a solution or a hint? Thanks in advance!
 A: 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. 
A: 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.
