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).
show/hide this revision's text 2 added 160 characters in body; deleted 156 characters in body; added 97 characters in body

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.

EDIT: retracted. Sorry. This is not (and cannot be made) decreasing. Missed that requirement.

show/hide this revision's text 1

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.