This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope to use graph theory as a vehicle by which to convey a sense of developing "advanced" mathematics (remember, these students will have seen first-year calculus, at best).
What are you favorite interesting and accessible nuggets of graph theory?
"Interesting" could mean either the topic has a particularly useful application in the real-world or else is a surprising or elegant theoretical result. An added bonus would be if the topic can reveal gaps in our collective knowledge (for example, even small Ramsey numbers are still not known exactly). "Accessible" means that a bright, motivated student with no combinatorial background can follow the development of the topic from scratch, even if it takes several lectures.