Ramsey Theory. I show them the proof that R(3) = 6 in the context of friends and strangers at a party. We talk about $R(k,l)$ and $R(2,k)$ as a sanity check. I prove that $R(k,l) \leq R(k-1,l)+R(k,l-1)$. I get them to find R(3,4). I show them the graph that gives the lower bound for R(4,4), and mention the connection to number theory. So, with the result above, that computes R(4,4). At this point, I show them the famous Erdos quote about R(5) and R(6):

> Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. 

At this point I like to either mention Ramsey theory on infinite graphs, talk about the connection to Van der Waerden (on arithmetic progressions) and Hales-Jewett (on hypercubes), or show them Erdos's proof of the exponential lower bound on R(k,k). This last one, via the **probabilistic method**, is my favorite, and only requires extremely basic probability (namely, the fact that in a finite outcome space, the probability of an event E is strictly positive if and only if there is an outcome in E). It also shows them a non-constructive existence proof, and I think that's very worth seeing.