Discrete Math - Day 57

Today we continued to explore graphs and their properties. I asked the class about the problem of creating a graph with two vertices of degree 2 and three vertices of degree 3. Students didn't have any additional comments. I left this to come back later as we explored specific properties in more depth.

I then reviewed some definitions, specifically paths, circuits, Euler paths, and Euler circuits. It had been a few days since we dealt with these terms and I knew that the class would be shaky on these terms and we were going to make use of them in the first two problems we worked on. Once these terms were clarified, we moved on to two problems.

The first looked at creating a graph with eight vertices and 6 edges. The graph could not contain any circuits. This problem proved a little challenging at first because students thought a circuit meant all of the edges were involved. When they realized a circuit could be just part of the graph they quickly found solutions to this problem. We shared out a variety of solutions that included graphs with one vertex of degree zero; two components, one of which had two vertices of degree 1; and two components, both containing four vertices. It is helpful for students to see the variety of solutions that can exist for a given description.

The next problem proved even more difficult for students to solve. The requirement was a graph with exactly three edges that did not contain an Euler path. The definition of Euler path was revisited and this helped students to better understand paths, circuits, Euler paths, and Euler circuits. They tried tackling this without success for several minutes.

There were many different attempts at a solution. The issue that kept arising is that no Euler path existed if you started at a specific vertex but one would exist if you started from a different vertex. As these issues were pointed out, the frustration level grew. Students started to think it was not possible.

Finally, one student modified a graph so that all three edges emanated from a single vertex. In this situation, the graph had three edges but required a doubling back on one edge in order to traverse every edge and, so, fit the criteria. When the class was shown the solution there were many "ah-ha's" around the room.

From here, we moved to the issue of summing the degrees of all the vertices in a graph. The question was if graphs always had to have a sum of degrees that was even. Students started looking at previous graphs they had drawn and creating new ones in the hope of drawing a graph whose sum of degrees was odd. Finally, a student asked if the sum always had to be even because every time you connected an edge between two vertices, each vertex would add one degree, resulting in a net increase of two degrees. This idea was shared with the rest of the class and everyone agreed that, yes, it made sense that you could never get a sum total that was odd.

The next problem asked if you could have an odd number of vertices of odd degree. Students were a bit baffled by the wording posted, so we discussed what this meant. I need to simplify the wording for this so it is more understandable the first time students read it.

I asked students to consider what was just demonstrated about the sum of degrees in a graph. A few students started to say this wasn't possible. When pressed, they voiced the idea that the sum of degrees would be odd which is not possible. This is precisely the idea for a proof by contradiction. I didn't bring this up at the time but will next class.

I used this result to revisit the graph problem of drawing a graph with two even vertices and three odd vertices. I asked students if this was possible. Students quickly saw that it was not possible because the sum of the degrees would be odd, which is not possible.

As class came to a close, students asked if we were going to continue working on these types of problems. I said we would, which they were glad to hear as they wanted more practice. This was the intent and we will continue to work on similar problems next class.

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