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 \ge 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.