# Sum that is 0 for Eulerian graphs

Suppose $E$ is a set of edges on graph $G$ over $n$ vertices, $\mathbf{x} \in \{-1,1\}^n$. The following seems to hold if G is not Eulerian, can anyone see a proof?

$$\sum_\mathbf{x} \prod_{ij\in E} x_i x_j=0$$

-

if G is Eulerian - as in you have one cyclic route that goes over all the edges, then the degree of each vertex is even so $\prod _{ij\in E} x_i x_j = \prod_{i\in [n]} x_i ^{deg(i)} = 1$ and so the total sum is $2^n$.

if by eulerian you refer to a route that is not a circle then you have exactly two vertices with odd degree so $\prod _{ij\in E} x_i x_j = x_s x_t$ and it is easy to see that $\sum_x x_s x_t = 0$

-
I think this applies even if there is no Eulerian path. As long as there are at least two vertices of odd order the sum is 0. –  Ross Millikan Oct 23 '10 at 3:02
I don't think you need the graph to be Eulerian. You have a bunch of terms $x_i x_j$ for $i,j \in \{1,2,\dots,n\}$ and want the terms to add to zero as the various $x_i$ are $\pm1$. It is true for n=2 as there are no pairs of $x_i x_j$. If it is true for n, it will be true for n+1 because all the added terms are of the form $x_i x_{n+1}$ and the ones where $x_{n+1}=+1$ cancel the ones where $x_{n+1}=-1$.