Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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$

share|improve this answer
    
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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.