September 7-11: Graph Theory

This week we will be discussing Euler circuits and paths.  Last week, we talked about tracing a graph.  An Euler path or circuit is what you get when you can trace a graph.  An Euler path is a path that uses every edge of the graph exactly once.  (Think "E" for Euler and edge.)  An Euler circuit is just an Euler path that begins and ends at the same vertex (so is a circuit).  Euler's Theorem will be an important theorem for us.  It will give us a quick way to determine if a graph has an Euler path or Euler circuit.  You will need to memorize this theorem.

Challenge Problem: The picture below is the floor plan for a section of prison rooms.  If all the doors are open, is it possible for a guard to enter this section at the entrance, pass through each door locking it behind him, and then exit without ever having to open a door that has been previously locked?  Answer by turning this into a graph theory question.  You may describe your graph by giving the vertices and edges or post a picture of your graph in your blog.  Your solution should include a path in the graph you create.