Paths and Circuits, by Michael Naylor

A foray into graph theory will show your students how points in space relate

Graph Theory and Topology are two branches of mathematics which deal with how points in space are related to each other. Many of the ideas from these areas are accessible to kids – and not only are the topics fun and exciting, but they also build spatial sense, logical reasoning and problem-solving skills.

The following activities can be done with students at any grade level. Younger children will enjoy the challenge of tracing and recreating these designs and older children can analyze the designs to learn important ideas about graphs, as well as learn a little bit of math history. Enjoy!

The Envelope: (Grades K-8)
Draw this figure on the board and challenge your students to draw it without lifting their pencils off the paper and without retracing their path.

This classic puzzle has stumped elementary kids for generations. The envelope can't be drawn unless you choose the right place to start (the lower left or lower right corner).

Why these places? Notice that when you enter and leave an intersection, or "node," you use up two pathways from that node. If a vertex has an odd number of edges connecting to it, it must either be a starting or ending point. Have your students count the number of edges meeting at each intersection in the envelope. The top three intersections each have four edges connecting, the bottom two have three. Therefore, the bottom corners are starting and ending points.

Each intersection or "node," is labeled with the number of edges connected to it.

Find the Paths (Grades K-8)
Here are several puzzles for your students to try. If you'd like them to find the rule on their own, have them first find solutions by trial and error. Ask: Which graphs start and end at the same point? Which graphs start and end at different points? Which graphs have no solution? Tell your students there is an important relationship between the number of connections at each intersection and where the starting and ending points are. Show them how to count connections (it helps if you draw the dots on each intersection as shown in the figure) and have your students label all of the intersections with numbers and describe how many edges meet at each intersection.

The key ideas are:

• If the paths start and end at different places, then those nodes will be odd.

• If all of the nodes are even, then the path will start and end at the same place and it doesn't matter where you start.

Solutions

1. All nodes are even – start anywhere, finish at the same point
2. Also all even
3. Two odd nodes – one is the "stem" of the grapes
4. Two odd nodes
5. Four odd nodes – impossible
6. Two odd nodes

The Bridges of Königsburg
This is a famous historical problem. Give your students hard copies of the map shown here. Tell them it's a map of the bridges in Konigsburg, Prussia.

Have your students try to find a path that crosses all of the bridges only once without swimming through the river. The task is impossible! If you think about each island as an intersection and all the possible exits as edges, you can change the problem to a graph problem as shown in the graphic.

Now the goal is to find a path on the lines of the graph that traces every edge without retracing. Since there are four intersections, and each has an odd number of edges, there are four places that are either starting or ending points. Thus, it's impossible to do with just one line.

For a worksheet featuring The Konigsburg Bridge Problem click here. PDF 89KB

Michael Naylor is a professor of math education at Western Washington University, Bellingham, WA.