Well, as it stands isn't the answer No? Just take $p(n) = 1$ if $n$ is even and $0$ if $n$ is odd. The graph will have at least two components consisting of the even and odd integers.