Let GGG be a finite connected undirected graph with nnn vertices and mmm edges. Prove that the number of subsets SSS of the edges of GGG such that every vertex of GGG has even degree in the subgraph (V(G),S)(V(G), S)(V(G),S) is exactly 2m−n+12^{m-n+1}2m−n+1.
You can write formulas in LaTeX or in plain text, and write your solution in any language.