# 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$.

-
Typo on my part, it should've said not Eulerian. When graph is Eulerian, the sum is 2^n as Prometheus points out –  Yaroslav Bulatov Oct 22 '10 at 22:03
The typo is not the problem with my answer. This is shown by the fact that I asserted it for all graphs. Prometheus' answer applies to all non-(Eulerian cycle) graphs, with or without a Eulerian path. –  Ross Millikan Oct 23 '10 at 4:09
Maybe some terminology confusion? What I was asking for was proof of 4.3.4 in yaroslavvb.com/upload/eulerian-expansion.png (this is Welsh's "Complexity..." book). Since G is arbitrary, the statement is equivalent to "sum is 0 if and only if A is Eulerian graph" –  Yaroslav Bulatov Oct 23 '10 at 18:04