Motivation:

Standards:

Materials:

1. County road cards.
2. "Instructions for Achieving Bliss" overhead.
3. Overhead image of the state of Bliss.
4. Contemplation handout for each county.
5. Handout of graph application problems, and handout of solutions.

Lesson Plan:

1. Distribute all the county road cards. If you don't have 30 people, use chairs for some of the cities. Just put the city card on the seat or tape it to the back of the chair. Also, place the Instructions handout on the overhead. If you have many less than 30 students, eliminate one or more of the colors from the stack of cards.

2. Allow the students, following the instructions, to connect themselves into a map of the state of Bliss. Each city card contains the city name on one side, and a list of the cities to which it is directly connected via a road, on the other. The students should connect themselves with rope to the people holding the cities on their list. (If you've borrowed our kit, use the color-coded plastic rings to represent each city, and have the children connect the ropes to the rings instead of to themselves. Each child representing a city can hold the corresponding ring. All cards of the same color are in the same county, and these cities, when they appear on the list, are written in plain type. Each different color card represents a different county. When a city of a different county appears on a player's list, it is underlined. Players should use white rope to connect cities within counties, and yellow rope to connect cities in different counties. We suggest that the yellow ropes be approximately 10 ft., and that the white ropes be no longer than a few feet. The children should first make connections to cities within the same county (same color), before connecting to other counties. Also, if city A and B are connected, for example, then each will appear on the list on the back of the other's card. These represent the same connection; only ONE ROPE should be used to connect city A to city B.
3. When all connections are made, place the map of Bliss on the overhead and ask the students if it's the same as their configuration. They will probably look quite different! Explain that this particular structure only describes connectivity, not necessarily geography. The rope lengths don't correspond to distances as we commonly refer to them.
4. So what is the structure? It's called a graph, and it is made up of vertices (the cities), and edges (the roadways). (These are also sometimes called nodes and arcs, respectively.) Graphs can be used not only to represent physical relationships (cities linked via roads, computers or telephones linked via network lines), but also to represent logical relationships, biological relationships, arithmetic relationships, temporal relationships, just-about-any-relationships. (We'll see examples shortly.)

   How can a computer "see" or "understand" a graph? We have already seen how to represent a graph as a list of connections. Each vertex (city) has associated with it a list of the other vertices to which it is connected (an "adjacency" list). The list of city names on the back of each card is the adjaceny list for that city. To demonstrate this representation, give the students the following list, and ask them to draw the graph that it describes. Ask them which county graph it corresponds to (Orange county).

   VERTEX	CONNECTED TO
   1	4, 5, 6
   2	4, 5, 6
   3	4, 5, 6
   4	1, 2, 3
   5	1, 2, 3
   6	1, 2, 3

   Notice that vertex 6 is listed as one of the vertices connected to vertex 1, and vertex 1 is listed as one of those connected to vertex 6. These two entries come from the same edge - the one connecting 1 and 6.
5. What if there were one-way roads in Bliss? Yes, we'd draw an arrow (called a directed edge) showing the direction that the edge points. Graphs with directed edges are called directed graphs. (In a directed graph, if the list for vertices connected to vertex 1 contains vertex 6, it need not be the case (but it might be) that the list for vertices connected to vertex 6 contains vertex 1.) We'll see examples of directed graphs soon.
6. Discussion, still using the overhead: (students can sit) What can we tell about the state of Bliss? (The overhead doesn't have city names on it, but the students can help you find the towns on the map.)
• Can we tell how far it is from McCook to Kearney? Not exactly, though we can tell how many different roadways we use in any walk between them. From now on we'll refer to the number of roadways between any two cities as the distance between them. This is the same as saying that all the roads are one unit long.
• Which city has the most traffic? Again, we can't tell exactly, but we can guess based on which city has the most roadways adjacent to it. Asking this question about Bliss is the same as asking which node has highest degree in the graph representing Bliss. The degree of a node is just the number of edges adjacent to it.
• What is the shortest route from Stockville to Hastings? This is a harder question. You can't be sure of the answer just by looking at the graph for a second, but you may be able to come up with a system for finding the answer.
7. Next have the students untie the county ropes and pass out the Contemplating Bliss handout, one or more to each county. Let the groups analyze their county graph using the questions on the handout as a guide.
8. The county graphs are designed so that they're each interesting in some classical way. Allow each group time to briefly express to the entire class what they think is "special" about their graph. Here's what we hope they will say (if they don't mention these characteristics, point them out):
• Red - First, the graph is not connected, which means you can't get from every vertex to every other. Second, no edge can be added to the group of 4 vertices (nor actually to the group of 2) because every possible edge is already included. Such a graph is said to be complete. Are any of the county graphs complete? Answer: no, you can add an edge to each one.
• Orange - This is the hardest one. The vertices can be separated into two groups so that no vertices within groups are attached. In other words, the vertices can be divided into two groups so that all the edges cross from one group to the other. Such a graph is called bipartite. Are any of the other county graphs bipartite? Answer: Yes, green and blue are. Let the students figure out how.
• Yellow - First, this graph can be drawn without crossing any edges (but there may also be ways to draw it with crossing edges). Such a graph is called a planar graph. Which of the other county maps are planar? Answer: all but Orange. Second, when this graph is drawn in the plane so that no edges cross, if you put your pencil in any region (not on an edge or vertex), the boundary around that region is made of 3 edges. Such a graph is called a triangulation (even though the regions may not look like triangles).
• Green - This graph is a cycle. The graph can be drawn with vertices arranged in a circular pattern, and edges only connecting each vertex with the vertex to its right and to its left.
• Blue - This graph is a tree. There are no cycles, and the graph is connected. If any edge is removed, the graph is no longer connected.

---

9. Say something like, "Whew. We've learned a lot about the structure of graphs, now let's talk about the things they're good for! Select a number of different graph usage problems, and distribute them to your students, who can either work in pairs or independently. Be sure to suggest the questions given at the top of the sheet, as points to think about when trying to represent one of the problems or situations as a graph. In some cases, there is some problem to be solved (e.g., "how can I get from McCook to Kearney?". Ask them to explain the relationship between the solution for the original problem, and the solution for the problem represented as a graph. (In this case, in the graph we'd look for a path (a sequence of edges) leading from McCook to Kearney). You should probably do a few examples first for the students. In particular, it will be helpful to do an example for each "type" of graph modeling problem. (A useful one to go through with them is the one involving the man with the boat, fox, chicken, and seed.) Allow the students plenty of work time.
10. Ask for volunteers to demonstrate their graph example. It is both fun and enlightening to see a variety of models.

Conclusion:

Evaluation:

The graph examples completed by the students should reflect their understanding of the material. Use a simple rubric to assess the model writeups. An example rubric: 3 points for a clear correct solution, 2 points for a correct but disorganized solution, and 1 point for an incorrect attempt.

Extensions: