I am interested in theorems with unexpected conclusions. I don't mean an unintuitive result (like the existence of a spacefilling curve), but rather a result whose conclusion seems disconnected from the hypotheses. My favorite is the following. Let $f(n)$ be the number of ways to write the nonnegative integer $n$ as a sum of powers of 2, if no power of 2 can be used more than twice. For instance, $f(6)=3$ since we can write 6 as $4+2=4+1+1=2+2+1+1$. We have $(f(0),f(1),\dots) = $ $(1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,\dots)$. The conclusion is that the numbers $f(n)/f(n+1)$ run through all the reduced positive rational numbers exactly once each. See A002487 in the OnLine Encyclopedia of Integer Sequences for more information. What are other nice examples of "unexpected conclusions"?

4$\begingroup$ I'll send you a shirt: thenerdiestshirts.com/blog/mathshirtcw/#more116 $\endgroup$– Douglas ZareMar 13 '10 at 21:48

2$\begingroup$ Thanks for great shirt! I guess it's difficult to make precise the difference between "unintuitive" and "unexpected conclusion." Some examples are at math.dartmouth.edu/~pw/solutions.pdf. Another nice example is the cake icing problem (demonstrations.wolfram.com/TheCakeIcingPuzzle). $\endgroup$– Richard StanleyMar 13 '10 at 22:47

11$\begingroup$ Stolen from Kevin Buzzard's comment at mathoverflow.net/questions/15050/linearalgebraproblems: If A and B are real n x n matrices, A^2+B^2=AB, and ABBA is invertible, then n is a multiple of 3. $\endgroup$– Jonas MeyerMar 13 '10 at 23:14
My favorite example of this phenomenon is Goodstein's Theorem.
Take any positive number $a_2$, such as the number $73$, and write it in complete base $2$, which means write it as a sum of powers of $2$, but write the exponents also in this way.
$$a_2 = 73 = 64 + 8 + 1 = 2^{2^2+2} + 2^{2+1} + 1.$$
Now, obtain $a_3$ by replacing all $2$'s with $3$'s, and subtracting $1$. So in this case,
$$a_3 = 3^{3^3+3} + 3^{3+1} + 1  1 = 3^{3^3+3} + 3^{3+1}.$$
Similarly, write this in complete base $3$, replace $3$'s with $4$'s, and substract one, to get
$$a_4= 4^{4^4+4} + 4^{4+1}  1 = 4^{4^4+4} + 3\cdot 4^4 + 3\cdot 4^3 + 3\cdot 4^2 + 3\cdot 4 + 3.$$
And so on. The surprising conclusion is that:
Goodstein's Theorem. For any initial positive integer $a_2$, there is $n>2$ for which $a_n=0$.
That is, although it seems that the sequence is always growing larger, eventually it hits zero. Our initial impression that this process should proceed to ever larger numbers is simply not correct. Indeed, a stronger version of the theorem, with essentially the same proof, allows one to replace the current base with any desired larger base, rather than merely increasing it by $1$ at each step.
To prove Goodstein's theorem, one can use the transfinite ordinals to measure the complexity of the numbers that arise. For example, our initial number $a_2=73$ is associated with the ordinal $\omega^{\omega^\omega+\omega}+\omega^{\omega+1}+1$. One then proves that these associated ordinals strictly descend at each step, because of the subtracting one part. Thus, it must hit zero, and the only way this happens is if the number itself is zero. One can see that we had to split up the complexity of the number in moving from $a_3$ to $a_4$, and this causes the associated ordinal to strictly descend, even though in this case the actual number happened to get larger. Eventually, the proof goes, the complexity drops low enough that the base exceeds the number, and from this point on, one is just subtracting one endlessly.
This conclusion is very surprising. But this theorem actually packs a onetwo punch! Because not only is the theorem itself surprising, but then there is the following surprise followup theorem:
Theorem. Goodstein's theorem is not provable in the usual Peano Axioms PA of arithmetic.
That is, the statement of Goodstein's theorem is independent of PA. It was a statement about finite numbers that is provable in ZFC, but not in PA.

2$\begingroup$ My favourite example is definitely Goodstein's Theor...*doh*. Yeah, definitely a nice exampleyou beat me to it :). Although when you actually write down the proof that the sequence converges to 0 starting at 4=2^2 you begin to get a very clear picture as to why it's true. $\endgroup$ Mar 13 '10 at 22:42

10$\begingroup$ There is another sense, however, in which the whole theorem is more than any given case: all of the particular cases are provable in PA. What remains unprovable is the universal statement. $\endgroup$ Mar 14 '10 at 0:02

11$\begingroup$ I once went through the trouble of find an explicit formula for G(n), the number of steps that the process takes to reach 0 starting with n. For example, G(3)=6, as the sequence is 3=2+1,3=(3+1)1,3=41,2,1,0. We have G(0)=1,G(1)=2,G(2)=4,G(3)=6,G(4)=3x2^4026532112, a number with 121210695 digits. The number of digits of G(5) is much larger than G(4), while (as I am fond of saying at this point) the number of elementary particles in the universe is estimated (well) below 10^90. I don't think one really understands what "fast growing" means until faced with something like this example. $\endgroup$ Jun 27 '10 at 21:43

1$\begingroup$ <3 Goodstein's theorem. I hope to one day understand the independence result. $\endgroup$– luquiApr 25 '11 at 4:01

7$\begingroup$ An even more impressive form of Goodstein's theorem is obtained by replacing "increase the base by $1$" at each step by "increase the base as much as you want (to any larger natural number)." The result still holds, with the same proof. I think this may have been Goodstein's original version. The "increase base by $1$" version became better known because, though weaker, it's still strong enough to be unprovable in PA (and it can be formulated in the language of PA). $\endgroup$ Sep 6 '15 at 8:22
I learned this example from Noam Elkies's excellent article The Klein Quartic in Number Theory. Elkies observes that Siegel's 1968 paper Zum Beweise des Starkschen Satzes, in order to prove its main result, proves what is equivalent to the following.
Theorem: Suppose that the only Fibonacci numbers which are cubes are $0, \pm 1, \pm 8$. Then the set of negative integers $d$ such that $\mathbb{Q}[\sqrt{d}]$ has class number $1$ is $\{ 1, 2, 3, 7, 11, 19, 43, 67, 163 \}$.

7$\begingroup$ @QY: It is indeed an excellent article, one of my alltime favorites, in fact. But it is by Noam Elkies, not Barry Mazur. $\endgroup$ Mar 14 '10 at 0:02

3$\begingroup$ Whoops! I was reading a different excellent article by Barry Mazur today and got confused. $\endgroup$ Mar 14 '10 at 2:16

2$\begingroup$ Is it true that the only Fibonacci numbers that are cubes are $0, \pm 1, \pm 8$? I seem to recall a recent paper proving this... $\endgroup$ Mar 14 '10 at 4:37

3$\begingroup$ Thanks. The papers listed in the answers to that question is the one I remember seeing. So this means that the Theorem above is a true theorem. $\endgroup$ Mar 14 '10 at 6:01

2$\begingroup$ @Anonymous: the class number 1 result was proved independently of any statements about Fibonacci numbers by Baker, Stark and HeegnerBirch. $\endgroup$ Mar 14 '10 at 8:11
I like Sharkovskii's theorem. It says that there is an explicit ordering of the natural numbers such that if $f:\mathbb{R}\rightarrow \mathbb{R}$ has a periodic point of least period m and m precedes n in the above ordering, then f has also a periodic point of least period n.

3$\begingroup$ Nitpick: you forgot to state that $f$ must be continuous. $\endgroup$ May 18 '11 at 11:53
It is well known that a group $G$ can't be written as the union of two proper subgroups. On the other hand there are groups that can be written as the union of three proper subgroups, my favorite one the quaternions $Q_8$. Now, I remember the following fact from my undergrad group theory class: if $G$ is a finite group such that $G$ is the union of three proper subgroups then the Klein four group $V_4$ is a quotient of $G$.

$\begingroup$ Ken Kramer first gave me that result as a homework problem years ago in my honors abstract algebra courseI'd completely forgotten about it! Good one! $\endgroup$ Apr 13 '10 at 2:26

3$\begingroup$ It's the starting point of my master thesis! :) see here: math.unipd.it/~mgaronzi/… Using this language, V_4 is the unique sigmaelementary group of sum 3. See the tabular at page 10, first line. $\endgroup$ Jan 3 '12 at 17:53

$\begingroup$ How extensive is the class of examples of groups that are the union of three proper subgroups? $\endgroup$ Mar 26 '20 at 4:44
I have always found Kuratowski 14set problem among the most surprising elementary theorems I know. Why 14?! (This was recently discussed in this MO question.)

$\begingroup$ What? That's a famous theorem? I remember being given this as homework in topology class... $\endgroup$ Sep 6 '15 at 13:14

$\begingroup$ I hadn't bothered to work through this until recently, but didn't find it very surprising. It's immediate that (for $k =$ closure, $c =$ complement) the relations $k^2 = k$ and $c^2 = 1$ imply that formal words in $k, c$ are reducible to alternating words, and then it's not that unexpected that alternating a certain number of times produces an operation that is idempotent or stable (here $kckc$, whence hitting $kckckckc = kckc$ with $c$ on the right gives $kckckck = kck$). At that point one sees that irreducible alternating words are length 7 or less, and there are in fact 14 such. $\endgroup$– Todd Trimble ♦Sep 6 '15 at 15:19

$\begingroup$ I never understood what's the fuss about this. $14=2^42$, the 2 you subtract here relate to the empty set and the full space. $\endgroup$ Jul 16 '17 at 8:17
Suppose $f(z)$ and $g(z)$ are two functions meromorphic in the plane. Suppose also that there are five distinct numbers $a_1,\ldots,a_5$ such that the solution sets $\lbrace z : f(z) = a_i\rbrace$ and $\lbrace z : g(z) = a_i\rbrace$ are equal. Then either $f(z)$ and $g(z)$ are equal everywhere or they are both constant.

3$\begingroup$ In the same spirit, Picard's Theorems: An entire holomorphic function is either polynomial or achieves every complex number but one infinitely many times. $\endgroup$ Jun 14 '11 at 20:44
If arbitrary products of nonempty sets are nonempty, then you can decompose a unit ball in $\mathbb R^3$ into finitely many pieces and rigidly reassemble then into two balls of radius 1. That is, the axiom of choice implies the BanachTarski paradox.
Of course, there are plenty of other results which depend on the axiom of choice, and many of them qualify, whether their conclusion seems to violate physical intuition or not. The point is that the conclusion seems nothing like the assumption.
Faltings' theorem (a.k.a. the Mordell conjecture): Given a smooth projective curve $X$ defined by an equation with rational coefficients, if the set of complex points on $X$ is topologically a surface of genus greater than $1$, then there are only finitely many points on the curve with rational coordinates.
(Actually it is proved for curves over finite extensions of $\mathbf{Q}$ too.)

$\begingroup$ It is still not understood how to find those finitely many rational points, even in principle. And the conjectured higherdimensional analogues are proved in only the most limited of cases, and they may even be false. $\endgroup$ Mar 14 '10 at 2:14

$\begingroup$ Why do you consider the Mordell conjecture as surprising, but the MordellWeil theorem as not? In any case, both are true only over finitely generated fields/rings. So there is indeed some finiteness assumption in the hypothesis. $\endgroup$ Mar 14 '10 at 3:06

12$\begingroup$ What is surprising is that the geometry/topology of the set of complex points has such a profound influence on the set of rational points. Why this should be the case is not so easy to explain. The MordellWeil theorem is somewhat surprising too, but here at least the role of the geometric condition of genus 1 (plus existence of a rational point) is clearer; namely, it implies that the curve is an algebraic group. (And also the MordellWeil theorem is much easier to prove.) $\endgroup$ Mar 14 '10 at 6:50

2$\begingroup$ My impression is that the genus gives a lower bound on the minimal degree of an equation defining the curve and then one finds that if g > 1 the degree of this defining equation is such that after homogenizing the equation, the notion that there are only finitely many integral solutions follows from a probabilistic argument (c.f. "Some probabilistic remarks on Fermat’s last theorem" by P. Erdos and S. Ulam). In view of these things the conclusion of Faltings' theorem doesn't seem so surprising to me. But maybe I'm missing something? After all I've heard many experts rhapsodize over it... $\endgroup$ Apr 24 '11 at 1:18
The TaniyamaShimura conjecture (now proved, by Wiles and others): all elliptic curves over $\mathbb Q$ are modular. It's magical that one can give a "formula" for the numbers of points on the curve modulo $p$ using modular forms.

4$\begingroup$ This is a good example, since the conjecture was dismissed as implausible by many leading mathematicians for years after it was made. Even in retrospect it seems incredibly "lucky" to me, although it can be made to look more natural by reference to Weil's converse theorems. $\endgroup$ Mar 14 '10 at 6:48
How about Shelah's truly remarkable ${\aleph_\omega}^{\aleph_0}\leq 2^{\aleph_0}\cdot\aleph_{\omega_4}$ (and variations of it)?
After seeing various independence results in set theory it is very surprising that anything of this generality can be proved in ZFC. Hence the disconnect between the assumptions and the outcome is that there are no assumptions (beyond the usual axioms of set theory). And then there is the ever puzzling (open) question "Why the hell is it $\omega_4$?"
I think the question is very personal, in a sense that what is unexpected for one person or from one point of view, can be very straightforward from another. To further complicate the matter, the notion of what is "unexpected" changes over time. Let me give a couple of familiar examples to illustrate these points:
1) the evaluation of the chromatic polynomial of a graph at $(1)$ is equal to the number of acyclic orientations of the graph (up to a sign). When you (R.P. Stanley) published this theorem in 1973, I bet this was considered a remarkably unexpected result  the conclusion had seemingly nothing to do with the assumption. For people outside of combinatorics, it is probably still unexpected. However, these days, with all those numerous reciprocity theorems (many of which, undoubtedly, grew in part out of this result), it is much harder for a combinatorialist to think of it as "unexpected". Curiously, Wikipedia takes a middle course: prior to the statement of the theorem, it adds "perhaps surprisingly", wisely letting us form our own conclusions.
2) take the Fibonacci polytope defined as convex hull of 01 vectors in $\Bbb R^n$ with no adjacent ones. Then its volume is the number of alternating permutations divided by $n!$. Again, if one have never seen "combinatorial polytopes" whose volume is expressed in terms of the number of certain permutations, the conclusion is completely unexpected  there is no obvious connection between Fibonacci numbers and alternating permutations. But for those of us who have seen and studied these, this result is straightforward and a very easy exercise.

4$\begingroup$ Hey I guess the first time I saw quadratic reciprocity I was very surprised! $\endgroup$ Mar 14 '10 at 18:52
There is a theorem by Bernstein that I like:
If $f$ is a $C^{\infty}$function on the intervall $I$ such that $f$ and the derivatives of $f$ to every order are nonnegative on $I$ then $f$ is analytic.
An example would be $e^x$ which satisfies the assumptions and thus is analytic (on the whole real line).

$\begingroup$ Is it enough for the derivatives to be, say, bounded below? Can one get that $\sin x$ is analytic using an argument like this? $\endgroup$– 36minSep 26 '12 at 5:34

$\begingroup$ Well, you can actually get that the exponential function is entire by the argument, and from that you get that $\sin$ is analytic by Euler's formulas. Don't think that it is enough in general however that the derivatives are bounded from below. $\endgroup$– JohanOct 9 '12 at 9:52

1$\begingroup$ For a periodic function $f$ with all derivatives bounded below with a uniform bound $M<0$, one can use the result on a bounded interval $I=(0,b)$ containing a full period of $f$ by applying it to the function $f(x)+Me^x$. Similarly one can handle any interval that is not the entire real line. $\endgroup$ Jul 3 '13 at 17:13
Whitehead problem: Is every abelian group A with $Ext^1(A, \mathbb{Z}) = 0$ a free abelian group?
Let G be a group of order p(p+1), with more than one pSylow. Then p is either 2 or a Mersenne prime. (Indeed, G exists uniquely for each such p.)
One of my own I'm proud of: http://front.math.ucdavis.edu/0911.4941
Let H be a degree n hypersurface in nspace (yes, same n) over $F_p$. From H we may be able to construct many other subschemes, by decomposing, intersecting components, decomposing again, intersecting again, ...
If the number of $F_p$ points on H is not a multiple of p, then all these subschemes are reduced.
Logic/computability theory is quite good at turning up seemingly special processes with unexpectedly universal outcomes. Goodstein's theorem (already mentioned) is one example. Another is the Matiyasevich theorem that polynomials with integer coefficients produce all computably enumerable sets. One way to state this is that each c.e. set is the set of nonnegative values of such a polynomial.

7$\begingroup$ In particular there's a polynomial whose only positive integer output values are the primes! That always struck me as surprising (until I actually understood how to construct such a polynomial...). $\endgroup$ Mar 13 '10 at 22:43

2$\begingroup$ Kevin, is the example of primes particularly more surprising than many other c.e. sets? For example, the result John Stillwell mentions implies that there is a polynomial whose positive integer range is the set of halting Turing machine programs, and another polynomial whose positive range is the set of all theorems of mathematics (via ASCII codes, say), and another whose positive range is the set of (codes for) trivial words in a given finite group presentation. $\endgroup$ Mar 14 '10 at 4:29

4$\begingroup$ Of course it's not more surprising than any other c.e. setsthe difference is that you say "c.e. set" and some people just switch off, whereas if you say "primes" then you get to stun people who know full well that the primes are "random" but don't know any recursion theory :) $\endgroup$ Mar 14 '10 at 8:13

$\begingroup$ The existence of a polynomial whose positive integer values are all primes is indeed surprising. I can't help to ask: what important consequences follow from that existence? $\endgroup$ Mar 14 '10 at 15:37

1$\begingroup$ KConrad, the theorem is far from trivial, and is not just a trick, even though the polynomial is not irreducible. The general theorem (proved by the same "trick" as with primes) answers one of the Hilbert questions, open for most of the 20th Century. $\endgroup$ Mar 15 '10 at 13:30
A theorem of Erdos and Hajnal: Any graph with no 4cycles is countably colorable.
Now, admittedly, this conclusion is less surprising when you state the actual stronger theorem that this is a corollary to: Any graph which is not countably colorable must contain a copy of $K_{\aleph_1,n}$ for every finite n. But in particular it must contain a 4cycle, which is not only a surprising statement on its own but is also especially surprising considering that given $k$ and any finite $n$ there are finite graphs with girth at least $k$ and chromatic numberat least $n$, and that given $k$ and an arbitrary cardinal $\kappa$ there are graphs with odd girth at least $k$ and chromatic number at least $\kappa$. But, no 4cycles? Countably colorable!
Definition: Let $A$ and $B$ be selfadjoint matrices, with the partial order $A\ge B$ if $AB$ is positive semidefinite. If $A$ is selfadjoint with spectrum in the interval $[a,b]$ and $f\colon [a,b] \to \mathbb{R}$ is a realfunction, define $f(A)$ using the spectral theorem. The function $f$ is called matrix monotone if $A\ge B$ implies $f(A)\ge f(B)$ for all $A,B$ with spectra in the domain $[a,b]$ of $f$.
Loewner's theorem: A function $f\colon [a,b] \to \mathbb{R}$ is matrix monotone iff it has an analytic extension to the upper and lower halfplanes so that the each of these halfplanes is mapped into itself.
I was very surprised when I first saw that the product of all primes $p$ such that $p12n,$ is the denominator of Bernoulli number $B_{2n}$.
The existence of two nonisomorphic isospectral Riemannian manifolds "we can't hear the Shape of a Drum" can be deduced from the existence of two quasi conjugated subgroups of $PSL_2(7)$
Weil's conjecture (proved by Grothendieck) that the number of points of an algebraic variety over finite fields is dictated by the topology of the same algebraic variety over ${\mathbb C}$ (more precisely its Betti numbers).
BaezDuarte's criterium: If $1$ is in the closure of the subspace of $L^2([1,+\infty[,\frac{dt}{t^2})$ spanned by the {$\frac{t}{n}$} (fractional part), for $n\geq 1$, then Riemann Hypothesis holds.

$\begingroup$ The BaezDuarte criterion really does look unexpected; I had to look it up right away. Not least because the notion that John Baez had something to do with it was also unexpected (he didn't; BaezDuarte is a hyphenated surname). $\endgroup$– Todd Trimble ♦Sep 6 '15 at 14:19
Here's one I was reminded of recently. Recall that a projective plane is a triple $(P, L, I)$ where $P$ is a set of "points," $L$ is a set of "lines," and $I$ is a subset of $P \times L$ describing the incidence relations which satisfies certain axioms. A finite projective plane always has $n^2 + n + 1$ points for some $n$ which is known as the order of the plane. So far, so geometric and combinatorial.
Theorem (BruckRyser): If $n \equiv 1, 2 \bmod 4$, then $n$ is a sum of two squares.
This is still the only known general criterion for ruling out orders of projective planes! It's conjectured that $n$ must be a power of a prime (examples include the projective planes which occur as $\mathbb{P}^2 \mathbb{F}_q$), but it's not even known whether there exists a projective plane of order $12$.
(There is a "theorem with an unexpected proof" in this area as well. For finite projective planes, Desargues' theorem implies Pappus's theorem, but the only known proof goes through Wedderburn's little theorem!)

$\begingroup$ And the only nongeneral criterion known is that there isn't one of order 10. $\endgroup$ May 24 '11 at 19:59
If $f\colon [a,b] \to \mathbb{R}$ is increasing, then $f$ is differentiable almost everywhere [w.r.t. Lebesgue measure].
(We can further conclude that $f'$ is measurable and $\int_a^b f'(x)\ dx \leq f(b)  f(a)$, but it's the first part that struck me when I learned it.)
And sure it makes sense, but knowing how real analysis often is, one might think that there must be some increasing function that fails to be differentiable on a set of positive measure.
The following pearl by Jacobson can under no circumstances be left out from the list:
Let $\mathbf{R}$ be a ring with center $\mathrm{Z}$. Let us suppose that you can find $n \in \mathbb{N}_{>1}$ such that $x^{n}x \in \mathrm{Z}$ for every $x \in \mathbf{R}$. Then $\mathbf{R}$ is a commutative ring.
A good place to learn more about results of this kind is Herstein's Noncommutative rings.

$\begingroup$ I know of a slightly different theorem by Jacobson. The way you state yours, it sounds like the choice of n has to be uniform across the ring. The one I heard about says that if, for each x, there is an n(x) such that x^n(x) = x, then the ring is commutative. In one aspect this is less general than your version, since we require x^n  x = 0, but on the other hand the absolute freedom in the exponent was very surprising to me. $\endgroup$– PietroApr 24 '10 at 18:19

4$\begingroup$ You're right about the existence of that result, Pietro. Yet, according to Herstein: "that theorem as proved has one drawback; true enough, it implies commutativity but only very few commutative rings exist which satisfy its hypothesis." $\endgroup$ Apr 26 '10 at 0:18
Maybe by now no one thinks of it as counterintuitive, but what about Poincaré Duality?
The following formulation (for psuedomanifolds) might fit this question best:
If K is a finite simplicial complex satisfying:
 each n1 simplex lies in exactly two nsimplices
 any two nsimplices are connected by a chain of nsimplices, each intersecting the previous in an n1 dimensional face
 each simplex lies in some nsimplex
then the (mod 2) Betti numbers of K in complementary dimensions must be equal!
Here are three examples from combinaorics:
1) The Frankl Wilson' theorem (The paper can be found here). This theorem in extremal combinatorics has a large number of amazing applications: Explicit Ramsey constructions, applications in combinatorial geometry; applications regarding Shannon capacity of union of graphs and many more.
2) TrotterSzemeredi The result by Trotter and Szemeredi regarding the maximum number of incidences between points and lines in the plane had remarkable applications including one discovered by Elekes' to the productsum theorem.
3) The mod p product sum theorem by BourgainKatzTao had many surprising applications in many directions. (One reason for the wide applicability is that when you multiply matrices sums and products mix.)
Reciprocity/duality theorems may give you unexpected results if you don't expect the connections.
Dan Ranmas already mentioned Poincare duality. To clarify, Poincare duality is not just abstract nonsense. It fails for nonmanifolds like general abstract simlicial complexes. For a [mod $2$] oriented manifold of dimension $d$, the [mod $2$] homology in dimension $k$ is isomorphic to the [mod $2$] homology in dimension $dk$.
Quadratic reciprocity relates whether $p$ is a square mod $q$ with whether $q$ is a square mod $p$.
Weil reciprocity relates the values of a rational function $f$ at the zeros and poles of $g$ with the values of $g$ at the zeros and poles of $f$.
Stanley reciprocity relates a generating function for the lattice points in a convex cone with a generating function for the lattice points in the interior evaluated at reciprocal arguments.
How about the CookLevin theorem  boolean satisfiability is NP complete. Though the consequence that "if there exists a polynomial time algorithm for boolean satisfiability then all problems in NP can be solved in polynomial time" may fit the bill better!
I mean what does boolean satifiability have to do with finding hamiltonians on graphs or finding shortest roots in networks?!
Ivan

1$\begingroup$ I don't think SAT is a particularly surprising NPcomplete problem, given that it looks like some kind of logical deduction. Scott Aaronson said it best, though, at scottaaronson.com/blog/?p=152 : "There’s a finite (and not unimaginablylarge) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof of the Riemann Hypothesis." $\endgroup$ Jun 27 '10 at 21:03

3$\begingroup$ I think that if you knew NP completness existed already then you might guess that SAT is NP complete, however the really surprising thing is that there are so many different and varied NP complete problems. I also think that one has to bear in mind the fact that with hindsight many ideas look more obvious than they were at the time! $\endgroup$ Jun 28 '10 at 2:22
Polya's Theorem: Simple random walk on $\mathbb{Z}^d$ is recurrent for $d\leq2$ and transient for $d>2$.
There is also a nice connection between this theorem and infinite networks of resistors. It turns out that the resistance of the whole network $\mathbb{Z}^d$ (one puts a unit source in one point and takes away sinks to $\infty$) is finite iff corresppnding random walk is transient :)
One of my personal favorite theorems with an unexpected application is the AtiyahSinger index theorem. I don't know if the application can be labeled as "real" mathematics, but it is amazing how it works.
In the article An SU(2) Anomaly, Edward Witten shows that certain "SU(2) gauge theories" having an odd number of doublets of Dirac fermions are "mathematically inconsistent". In this case, the latter means that all path integrals vanish.
That all path integrals vanish is a consequence of the fact that $\pi_4(SU(2)) = \mathbf{Z}/2\mathbf{Z}$. Thus, there is also some homotopy theory involved!
For completeness, here is the reference E. Witten, An SU(2) Anomaly. Phys. Lett. B 117 (1982), pages 324328.