How Do You Mathematically Guard A Museum?
How colorful graphs solve this problem beautifully!
One of my favorite things about mathematics is how it can be applied to such a wide variety of situations. Unexpected problems can turn into a fun math puzzle that leads to a whole new series of theorems being discovered! I’ve written many articles about these situations before, and they are often my favorite topics to dive into.
A classic example of this is the museum problem. It was first posed by Victor Klee in 1973 and was solved later by Václav Chvátal, both pictured above. It is now considered a quintessential example of the usefulness and flexibility of graph theory. The museum problem has become famous because of how visually intuitive it is and how easy it is to understand. In this problem, we are given a museum as a series of rooms like in the examples below.
We want to know how many guards are needed to watch over this museum. For the purposes of this problem, a guard is represented as a…
