  Let $T(G;X,Y)$ be the Tutte polynomial for graphs. We study the sequence
$t_{a,b}(n) = T(K_n;a,b)$ where $a,b$ are non-negative integers, and show that
for every $\mu \in \N$ the sequence $t_{a,b}(n)$ is ultimately periodic modulo
$\mu$ provided $a \neq 1 \mod{\mu}$ and $b \neq 1 \mod{\mu}$. This result is
related to a conjecture by A. Mani and R. Stones from 2016. The theorem is a
consequence of a more general theorem which holds for a wide class of graph
polynomials definable in Monadic Second Order Logic and some of its extensions,
such as the the independence polynomial, the clique polynomial, etc. We also
show similar results for the various substitution instances of the bivariate
matching polynomial and the trivariate edge elimination polynomial
$\xi(G;X,Y,Z)$ introduced by I. Averbouch, B. Godlin and the second author in
2008. All our results depend on the Specker-Blatter Theorem from 1981, which
studies modular recurrence relations of combinatorial sequences which count the
number of labeled graphs.
