Discrete Math - Day 58

Today we continued working with graphs and their properties. I am pleased that the last week before finals and the seniors are still actively engaged with the material.

I briefly went over the two properties we looked at yesterday and talked about how the reasoning that a graph could not contain an odd number of odd vertices was an example of a proof by contradiction. I related this back to proving there was an infinite number of primes. In both cases, an assumption was made that led to a contradiction. This leads us to conclude that the assumption is false and therefore the converse of the assumption must be true.

We then looked at a series of problems. The first question was quickly dispatched. Students argued using the results from last class that a graph with five vertices of degree 1 or five vertices of degree 3 cannot exist because the sum of the degrees would be odd. They were also able to easily draw a graph with five vertices of degree 2.

The problem after this gave students more trouble. As one student said, "This was fun and now it's not." As students examined the problem they began to believe that it was not possible to draw a graph with eight vertices and 29 edges. Part of this feeling arose from the odd number of edges. They were at a loss at proving the graph could not be drawn.

I drew four vertices on the board and asked the class how many edges could be drawn connecting the different vertices. After some discussion and debate, one student said there could be 12 edges drawn. I started drawing out edges, three from each vertex. I pointed out that at some point I was duplicating an edge that was previously draw. Because I was double-counting the edges, I needed to divide by 2, resulting in a total of 6 edges.

I then asked students how many edges can be drawn when there are eight vertices. Again, there was a lot of discussion and debate. To help refocus their thinking I asked the class how many vertices could a single vertex be connected to? The response was "7". How many times can this happen? The response was "8". How many total edges does this represent? Silence. Then a couple of students responded that there would be 56, since 7 x 8 = 56. I asked if there were edges being double-counted? Students realized it was the same situation as with four vertices and saw that there were 28 edges.

The class still was not making a connection to the possibility of having 29 edges in the graph. I asked what the 28 edges represented? Students said that it was the number of edges in the graph. Was it possible to have any more edges in the graph? Students said no, because every vertex was already connected with every other vertex. It was at this point that students started to realize that this meant the graph could not have 29 edges.

I like this problem because it brings in some of the counting ideas that we used at the beginning of the semester. One student commented about being taught stuff that keeps getting reused and why couldn't it be like other math classes where the material just disappeared once you were done with it. I love that previous concepts can be brought to bear on new material or in new ways.

Students were given the degrees of six vertices and asked whether or not it was possible to draw graphs with those degrees. At this point, most students saw the first was not possible because the degrees summed to an odd number. For the second, they had some issues at first until they realized a simple graph did not have to be connected. Many struggled with the last graph as it required five vertices of degree 3 and one of degree 5. They began to believe it was not possible. I pointed out that the sum of degrees was even, so at least we couldn't rule out its impossibility on that basis. Finally a student said they found a solution, a pentagon with a vertex in the middle. The class response was oohs and aahs and comments of how they were copying that result down in their notes.

We looked at whether a graph with eight vertices could have a vertex of degree 0 and a vertex of degree 7. A few students quickly realized this was not possible as a degree 7 vertex would have to connect to every other vertex, which meant you could not have a vertex of degree 0. This was sound reasoning that was easy to understand. A nice little proof.

The final problem was an extension of the previous problem. Could a graph with eight vertices have each vertex with a unique degree value. Students felt like this could not happen but were having difficulty explaining why. I asked students what all the possible degrees of the vertices could be and the said 0-7. I wrote out on the board 0, 1, 2, 3, 4, 5, 6, 7.

Next, I asked what the last problem we worked on told them about the situation. They said that you could not have both a degree 0 and a degree 7 vertex. When asked which they wanted to eliminate the students suggested the degree 0. We now have possible seven possible degree values to allocate to the vertices: 1, 2, 3, 4, 5, 6, 7. There are eight vertices in the graph. By the pigeon hole principle, I cannot assign the eight vertices to the seven possible vertices without duplicating at least one degree value. This was another nice tie-in to the counting work we did at the start of the semester.

To close class, I asked students to record their thoughts on what was easiest to do when proving a statement or creating a counter-example. Then I asked students to consider what they could do in the future to help themselves when proving a statement or producing a counter-example.

We will continue to explore properties of graphs and look deeper into the ideas behind Euler paths and circuits.

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