Discrete Math - Day 60

Today we took practiced finding Euler paths and circuits.

I started class by reviewing the Euler theorems we looked at last class. I did this mostly for the benefit of those students who weren't here last time.

I then showed them Fleury's Theorem. This theorem basically says that if you have a connected graph that has either no odd vertices or two odd vertices, an Euler path can be found.

I showed a graph and labeled the degree of each vertex. The graph had four odd vertices, so Fleury's Theorem did not apply. I connected two of the odd vertices with an edge. Now the graph had the required two odd vertices. I followed the algorithm for Fleury's Theorem to demonstrate how it worked.

This led use to the next two theorems about graphs.

Second Euler Path Theorem

If a graph is connected and has exactly 2 odd vertices, then it has an Euler path.

Second Euler Circuit Theorem

If a graph is connected and has no odd vertices, then it has an Euler circuit (which is also an Euler path).


I pulled up the original graph I used for demonstration and said that the way I had connected the two odd vertices was akin to bulldozing through someone's backyard or house. The Eulerization of a graph results from adding multiple edges so the resulting graph now has either zero or two odd vertices. I asked students how an Eulerization of the graph could be accomplished. After a little thought one student offered a way.

With that, I handed out a sheet with three different graphs. They were to determine if an Euler path or circuit for each graph. If it did, they were to draw it. If it didn't, they were to explain why not and then create an Eulerization of the graph so that the revised graph would have an Euler path or circuit.

This exercise went well. The students worked on the problem, discussing terminology and results. Everyone seemed to grasp the basic concepts of what they should be doing. Everyone was able to identify degrees of vertices (although some students found they had to be more careful counting).

After briefly sharing out and discussing the results for these graphs, I passed out a more complex graph. Students were asked to Eulerize the graph if an Euler path or circuit did not exist. There were about five minutes left in class but students jumped right into the task. As students determined degrees of the vertices, they found there were two odd vertices. I would here comments like, "There are two odd ones, this should work, let's do this." It was encouraging to hear them so engaged and so confident in their knowledge.

The bell rang and everyone looked a bit surprised. They were so focused on the sheet they forgot how little time left in class.

We'll finish looking at their results next class. After, we'll start our review process for the final exam, which is taking place in less than one week.

Visit the class summary for a student's perspective and to view the lesson slides.