Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops.


Define 


$$P\_g(x\_1,\dots,x\_n) := Sym\left[ \prod\_{(i,j) \in g} (x\_i-x\_j) \right]$$


where $(i,j)$ is the directed edge from $i$ to $j,$ and $Sym$ denotes the symmetrization,
that is, sum of all permutations of variables in the argument.


Now, for some multigraphs $g,$ we have that $P\_g$ is identically zero.


A sufficient condition is that if we can change the direction of an odd number of edges in $g$
and obtain a graph isomorphic to $g,$ then $P\_g$ is identically 0.


This is however not necessary, as the graph with edges (1,2),(2,3),(3,4),(2,4),(2,4)
will give a polynomial that is identically 0.


The number of connected multigraphs with n edges that yields a zero polynomial 
are, for n=1,..,6, equal to 1,0,3,2,19,20, and this sequence gives no hits in Sloane.


What I am asking for is a necessary and sufficient condition of a graph that gives the zero polynomial, as defined by the procedure above.


EDIT: Note that if $g\_1$ and $g\_2$ are isomorphic as undirected graphs, 
then $P\_{g\_1} = \pm P\_{g\_2}.$ Changing the direction of one single edge changes the sign of the associated polynomial.



Symmetric polynomial from graphs
I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:


The question pertains to the classical invariant theory of binary forms.
Firstly, suppose your graph is $v$-regular, i.e., all vertices have the same valence $v$.
Then if the $x\_1,\ldots,x\_n$ are interpreted as the roots of a polynomial of degree $n$,
or after homogenization as a homogeneous polynomial of degree $n$ in two variables,
i.e., a binary form, your sum defines an $SL\_2$ invariant for such a binary form.
The nonregular case likewise corresponds to what 19th century mathematicians called
covariants.


Here is a fact. In the regular case, the product $nv$ has to be even since this is twice the
number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying
this condition the polynomial is identically zero.
Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that 
all graphs of this kind give zero. This is a nontrivial fact which has to do with
the invariants of the binary quintic: there is no skew invariant before degree 18 which is
the degree of Hermite's invariant.


Another example of your question is the following. Take $n=m^2$, and arrange the vertices
into an $m\times m$ square array. Take for the graph $g$ the following:
put an edge between two vertices if they are in the same row or in the same column.
It is trivial to see that the polynomial will vanish if $m$ is odd.
Now if you can prove that the graph polynomial is nonzero (for any even $m$)
then you would have proved the Alon-Tarsi conjecture, which implies the even case
of the Rota basis conjecture.
As far as I know these are widely open problems.


A reference on the general graph polynomial vanishing question is:
G. Sabidussi, [Binary invariants and orientations of graphs](http://www.sciencedirect.com/science/article/pii/0012365X9290607H), Disc. Math 101 (1992), pp. 251-277.


This very question was historically important for the development of graph theory since it motivated Petersen's work.


