Symmetric polynomial from graphs 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.
 A: 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, 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.
