[Math] Interesting and accessible topics in graph theory

big-listco.combinatoricsgraph theorymathematics-education

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.

Best Answer

I have found that the Art Gallery Problem engages middle- and high-school students, and quickly leads to the unknown, which itself can be eye-opening to students. (On the latter point, students tend to think of mathematics as settled, so it is nice for them to reach unsolved problems they can comprehend, which abound at the interface between geometry and graph theory.) Proving the traditional art gallery theorem (that $\lfloor n/3 \rfloor$ guards suffice and are sometimes necessary to cover an $n$-wall gallery) introduces triangulations and the chromatic number of a graph. There are many sources, including the recent book (if I may self-promote) Discrete and Computational Geometry.

                3-coloring

Addendum. May I also recommend "How to Guard an Art Gallery and Other Discrete Mathematical Adventures", by T.S. Michael, whom I had the pleasure of teaching two decades before his book was published.