Discrete Math - Day 56

We continued to work with graphs, attempting to draw them for specific criteria.

We focused on three problems today:

1. Draw a graph with three vertices of degree 2 and two vertices of degree 3.
2. Draw a graph with two vertices of degree 2 and three vertices of degree 3.
3. Draw a graph with one vertex of degree 1, two vertices of degree 2, three vertices of degree 3, and 4 vertices of degree 4.

I asked the class to work on these three problems. As I walked around, students were engaged, discussing different possibilities, clarifying definitions, and, in general, having healthy mathematical discourse. I saw that all the groups had completed the first task, many had made an attempt at the second problem, and some were working through but struggling with the third problem.

I decided to halt their work to look at their solutions to the first problem. I thought the break and looking at different solutions would help to maintain their focus and persevere through the other problems. The first solution gave students an opportunity to be creative. Students showed connected graphs with no multiple edges, disconnected graphs, graphs with multiple edges and graphs with loops.

Showing these allowed students to see that they might be able to use different approaches to obtain a solution for the remaining problems. The students continued to work on the last two problems, with most focused on the third problem. There were some tentative solutions and students were building graphs that could lead to a solution but they were not complete.

Since no group had created a graph fitting the description for the last problem, I asked a student who said he was close to share what he produced. As he was at the board labeling the degrees of the vertices and sharing what he produced, he and a couple of other students realized that the graph could be easily separated into two pieces to meet the criteria. As this option was discussed, other students concurred that this would work.

Another student had been building a graph but wasn't sure how to complete it to fulfill the requirements. The graph was put up on the board so we could discuss options as a class. The degrees of the vertices were labeled and it was discovered that three of the vertices had not been assigned the correct degree. Additional vertices and edges were added and several students became very involved in discussing how to continue the graph. Jointly, these students came up with a solution that worked.

Both of these discussions provided me some ideas as to assessment questions that I could use. Typically, I would just ask students to construct a graph with a given criteria. I think providing a graph and asking how the graph can be modified to meet the criteria or how the graph could be extended to meet the given criteria would be interesting.

After these two discussions, I asked the class about the second problem. A couple of students thought they had solutions and these were presented. In both cases, there was a vertex whose degree had been miscounted. Students worked on this problem a couple of more minutes without success.

I stopped students and asked if they considered if the graph was even possible to draw. Time was running out in class. I asked students to consider how graphs are put together and whether they could explain why the graph was not possible to draw or to produce an example of the graph.

This question is a good starting point for proof using graphs. We will look at drawing graphs with circuits and Euler paths next class and delve more deeply into trying to prove the existence of certain graphs.

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