show/hide this revision's text 3 edited body; edited body

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.
show/hide this revision's text 2 T.S.Michael's book.

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.
show/hide this revision's text 1 [made Community Wiki]

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