THE NUMBER OF LABELED CONNECTED GRAPHS MODULO PRIME POWERS

Let c(n) denote the number of vertex-labeled connected graphs on n vertices. Using group actions and elementary number theory, we show that the infinite sequence, c(n) : n >= 1, is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of c(n) and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph K-n at integer points.