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.