MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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