GraphPolynomial(G,x) returns a polynomial in the variables $x_1$,...,$x_n$ when x is a symbol and G is a graph with $n$ vertices. The polynomial consists only of linear factors of the form $\left(x_j-x_k\right)$ where $j$ and $k$ represent adjacent vertices.

If x is a list of algebraic expressions whose length is equal to the number of vertices of G, the polynomial is formed using linear factors of the form $\left(x\left[j\right]-x\left[k\right]\right)$ where $j$ and $k$ represent adjacent vertices.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{Graph}\left(\left[1\,2\,3\,4\,5\,6\right]\,\left\{\left\{1\,4\right\}\,\left\{2\,6\right\}\,\left\{3\,4\right\}\,\left\{3\,5\right\}\,\left\{4\,5\right\}\,\left\{4\,6\right\}\,\left\{5\,6\right\}\right\}\right)\:$

$\mathrm{GraphPolynomial}\left(G\,x\right)$

$\left(\mathrm{x1}-\mathrm{x4}\right)\left(\mathrm{x2}-\mathrm{x6}\right)\left(\mathrm{x3}-\mathrm{x4}\right)\left(\mathrm{x3}-\mathrm{x5}\right)\left(\mathrm{x4}-\mathrm{x5}\right)\left(\mathrm{x4}-\mathrm{x6}\right)\left(\mathrm{x5}-\mathrm{x6}\right)$

$\mathrm{GraphPolynomial}\left(\mathrm{CycleGraph}\left(4\right)\,\left[x\,y\,z\,w\right]\right)$

$\left(x-y\right)\left(x-w\right)\left(y-z\right)\left(z-w\right)$

Noga Alon and Michael Tarsi, "A note on graph colorings and graph polynomials", J. Combin. Theory Ser. B 70 (1997), no. 1, 197–201, doi: 10.1006/jctb.1997.1753

The GraphTheory[GraphPolynomial] command was updated in Maple 2019.