1
$\begingroup$

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

2 Answers 2

3

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$

  • 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.2010-10-23
1

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

  • 0
    Typo on my part, it should've said *not* Eulerian. When graph is Eulerian, the sum is 2^n as Prometheus points out2010-10-22
  • 0
    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.2010-10-23
  • 0
    Maybe some terminology confusion? What I was asking for was proof of 4.3.4 in http://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"2010-10-23