Related to the answer about NP-complete problems, there are a number of theorems that state "either x is true, or P=NP." The most interesting of these in my opinion are hardness of approximation results. For example: "Given two graphs on $n$ vertices, one with max clique size $n^\alpha$ and one with max clique size $n^{1-\alpha}$, there is no polynomial time algorithm that determines which is which, or P=NP."
Most results like this are proven via the PCP Theorem, by showing that if you can approximate a result to a certain extent, you can then convert that into a proof of the statement.