Motivation:

Materials:

1. Bridges of Konigsberg tarp or chalk on the grass or tape on the floor.
2. Bridges of Konigsberg overhead including overlays (1, 2, 3, 4) of vertices and edges (optional).
3. Bridges of Eulertown overhead including overlays of vertices and edges (optional).
4. Pencil puzzles - one copy per student.

Lesson Plan:

1. Explain the story: The town of Konigsberg, Prussia was divided into four sections by the branches of the Pregel River. In the 18th century seven bridges connected these regions as pictured at the end of this lesson. The townspeople took long walks through the town on Sundays. They wondered whether it was possible to start at some location in the town, travel across all the bridges without crossing any bridge twice, and return to the starting point.
2. Challenge the students to cross all 7 bridges exactly once, using the enlarged version of the bridges (on a tarp or grass).
3. Show the Bridges of Konigsberg overhead (or draw the picture on the chalkboard), and make sure the students recognize that it's the same picture they saw on the tarp or grass. Show how the Bridges can be represented using a graph. If you completed Lesson 10 (Graphs) ask the students how they think the problem should be represented. Answer: Each land region is a vertex (also called a node), and the bridges are edges (also known as arcs). If you have the overheads, use them to demonstrate the representation, with vertices representing the land masses and edges representing the bridges. If you don't have the overheads, show on the chalkboard how to "shrink" each land mass into a vertex, and thin the bridges until they become edges. Now the Bridges problem becomes:  "Is it possible to pass over each edge exactly once and return to the starting vertex?" This is the same as asking: "Is there an Eulerian Circuit?" (after Leonhard Euler (pronounced "oiler"), who was a prolific mathematician, the "father" of graph theory, and the first to solve this puzzle). Once you are sure all students understand the graph and problem, remove the original picture and just talk about the graph.

---

4. Discussion: how can we tell if there isn't an Eulerian Circuit? To help them think about the answer, pick a room in your building (excluding the room that you are in) that has one door (e.g., a bathroom or small office) and ask them how many times they have been through the doorway. When they say "who knows", tell them that even if you don't know what a number is, you can often still tell some things about it: Ask whether they've been through the doorway an odd or an even number of times. Help them discover that the answer must be "even" because if it was "odd", they'd be in that room right now!

   Now relate this to the current problem: Think of the edges leading to/from a vertex as doors. If you start at vertex A, and cross each edge once and arrive back to A for the last time, how many times in/out of some other vertex B have you gone? Must be an EVEN number of times - otherwise you would still be at B. So, every vertex except A must have even degree -- that is, an even number of edges connecting to it. How about vertex A? It must also have even degree if there is an Eulerian Circuit; lets count the number of edges connecting to it: You start at A and leave along some single edge (an odd number of edges used so far, since "1" is odd), and then each time you re-enter and re-exit you use up 2 more edges (adding 2 to an odd number keeps it odd), and finally, you re-enter for a last time, make the number of edges you've crossed that are connected to A even. More succinctly, each vertex must be entered and then left again as the edges are traversed, except for the starting vertex which is left and then eventually re-entered. Summarize by saying "There is no circuit if any vertex has an odd number of edges."

   ---

5. Given this discussion, ask the students if there is an Eulerian Circuit for the Bridges graph.  NO!
6. Next place the Eulertown graph on the overhead (or, draw it on the chalkboard) and ask if there is an Eulerian Circuit. The students should count vertex degrees and say, "NO!", since two vertices have odd degree.
7. Take your overhead pen or chalk, and starting at a vertex of odd degree, trace the edges, going over each one exactly once. Ask the students to explain what happened. The answer is that there is no CIRCUIT, but there is a PATH! An Eulerian Path is almost exactly like an Eulerian Circuit, except you don't have to finish where you started. There is an Eulerian Path if there are exactly  two vertices with an odd number of edges.  The odd vertices mark the start and end of the path.
8. More discussion: if every vertex has an even number of edges, is there necessarily  an Eulerian Circuit?  If there are exactly two vertices with an odd number of edges, is there necessarily  an Eulerian Path? Have them think about this as they solve the pencil puzzles. 
9. Distribute the pencil puzzles and allow the students to work on them. Encourage them to think about a system for finding the circuit or path in any graph. 
10. When everyone has worked through all the puzzles, ask students to come forward and show their solutions. 
11. Ask if anyone has a system for solving the puzzles. Here's an attempt at an explanation of the system.  We suggest explaining this to the students using overheads or the chalkboard. 

Pictures are much better.  In our pictures, the dotted lines are the edges which aren't yet included in the circuit, the bold edges are the new edges to add, and the regular edges are the circuit we've made so far.  Select any vertex to be the start and end of your circuit (we chose A). Begin at this vertex and traverse edges however you'd like, making a list of the vertices you hit! Eventually you will end up at the start vertex again. (We'll talk about why this is true in a couple sentences.) 

The current path:  ABCGFA  
Next, choose any vertex on the original circuit which has edges you haven't traversed yet (we'll choose vertex C). Begin at this vertex and traverse edges until you get back to it.  The current path:  ab CDEC gfa Now you have two circuits. Simply splice the second one into the first one (we replaced the C in ABCGFA with CDEC). The result is a larger circuit containing all edges in both circuits. 














Repeat this process until there are no edges left untraversed. 

The current path:  a BFEGB cdecgfa All edges are traversed so we're done!  Any questions?  Now, we owe you an explanation of why you'll end up where you started on each of the subcircuits. Notice that the instant you leave the beginning vertex, it becomes the only vertex with  an odd number of unused edges. There is nowhere else to end!! Any other vertex you visit you'll be able to leave again!  To find an Eulerian Path, just put in a temporary fake edge between the two vertices with an odd number of edges and follow the procedure above, starting with one of the odd vertices. (The students should practice this procedure on the pencil puzzles until they get the hang of it) 

This approach to solving the problem is known as a greedy approach because you can arrive at a solution to the entire problem by making the best (greediest) choice at each intermediate stage. In this situation, the greedy choice is simply to make each subcircuit as long as you can. 

12. Let the students make problems for each other.  Each student should create three graphs, one which has no path nor circuit, one which has a circuit, and one which has a path.  The students should exchange papers and then solve each other's graphs using the strategy described above.  Ask them to demonstrate the splicing of subcycles as we have done in the example.

Evaluation:

Extensions

Standards:

• NCTM K-4:  1, 2,  3, 4, 7, 9, 13.
• NCTM 5-8:  1, 2, 3, 4, 5, 12.
• NCTM 9-12:  1, 2, 3, 4, 7, 12.

Skills:

• Problem solving / reasoning / communication / connections
• Strategy development
• Multiple addition (any type of number)