
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
Motivation:
Consider a network of roads, for example. If it is possible to walk
on each road in the network exactly once (without magically
transporting between junctions) then we say that the network of roads
has an Eulerian Path (if the starting and ending locations on an
Eulerian Path are the same, we say the network has an Eulerian
Circuit). This activity examines the characteristics of such
paths and circuits. We study this problem because it is a
classic example of the kind of problem computers are particularly good
at solving.
Materials:

Bridges of Konigsberg tarp
or chalk on the grass or tape on the floor.

Bridges of Konigsberg overhead
including overlays
(1,
2,
3,
4)
of vertices and edges (optional).

Bridges of Eulertown overhead
including overlays of vertices and edges (optional).

Pencil puzzles  one copy per student.
Lesson Plan:

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.

Challenge the students to cross all 7 bridges exactly once, using the enlarged
version of the bridges (on a tarp or grass).

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.

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 reenter and reexit you use up 2 more edges
(adding 2 to an odd number keeps it odd), and finally, you reenter 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 reentered. Summarize by saying
"There is no circuit if any vertex has an odd number of edges."

Given this discussion, ask the students if there is an Eulerian Circuit
for the Bridges graph. NO!

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.

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.

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.

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.

When everyone has worked through all the puzzles, ask students to come
forward and show their solutions.

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.

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:
Have the students hand in the graphs they've designed for each other.
Assess the performance of the pairs, keeping in mind that success on the
second part of the exercise depends on the proficiency of the person who
creates the graphs in the first part. You may want the students to
cooperate to solve any problems which arise.
Extensions
It turns out that this theory underlies an extremely important skill:
the art of balloon animals! A balloon animal is "folded" out of a
long, skinny balloon. The result is a number of segments (edges),
joined at places where the balloon has been twisted (the vertices).
Any animal that is made from a single balloon has an Eulerian path; to
see it, simply follow the balloon from one end to the other through
the animal. Ask the students how they would represent balloon animals
using a graph, and make sure they understand how the balloon animals
relate to Eulerian Paths and Circuits. If a graph has an Eulerian
Path or Circuit, then the students can bend a balloon into the shape
represented by the graph!!
Here's an example of the
basic
balloon dog, and the underlying Eulerian path.
Standards:

NCTM K4: 1, 2, 3, 4, 7, 9, 13.

NCTM 58: 1, 2, 3, 4, 5, 12.

NCTM 912: 1, 2, 3, 4, 7, 12.
Skills:
 Problem solving / reasoning / communication / connections
 Strategy development
 Multiple addition (any type of number)
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
