Index

# Discrete Mathematics Project Graph Theory Activity

## Title

Euler and Hamitonian Circuits (Jim Arnow)

## Goals

1. Students will experiment to discover which graphs have Euler circuits and paths and which don't.
2. Students will generalize rules for the existence of Euler circuits and paths.

## Abstract

This activity, stated in the form of a puzzle, presents the students with the concepts of finding both Euler circuits and paths. Students will be presented with various graphs and asked to draw them according to the various requirements. In some cases, these problems will have no solution. The exercises attempt to lead the students towards Euler's famous result motivated by the seven bridges of Konigsberg (now called Kaliningrad.)

## Problem Statement

As a bridge inspector, you must cross each of the bridges in the city of Konigsberg once to inspect them. Since you have to do this every day, as a challenge you decide to see if you can cross each bridge once and only once, and end where you started. Using a map of the town, can you manage this?

## Instructor Suggestions

1. Present the students with a picture of Konigsberg or the "Unsuspecting Bridge Inspector" handout. Note that many pictures of Konigsberg include more or less than the seven bridges that were present when Euler examined this question.
2. Ask the students how they could model the situation presented to Euler. Through the course of this discussion, introduce the graph model for the situation.
3. Have each student copy the corresponding graph onto a sheet of scratch paper. On their own, have each one attempt to come up with a circuit that crosses each bridge once and only once and finishes and starts at the same location.
4. When it is discovered that no such circuit exists, divide the students into small groups. On an overhead, present them with a set of graphs which either have an Euler circuit, have an Euler path or have neither. Direct each group to try to come up with a rule for determining when such a path exists. If the examples given are not enough for them to come up with a rule, have them create their own examples.
5. When all groups are completed, have each group present their results to the class. When a rule is agreed upon by the class, write it up on the board.
6. Now, ask the students to return to their groups and for those graphs which do not have Euler circuits, have them attempt to find Euler paths and a rule for their existence. If they want to use the same worksheets, they may use different color pencils.
7. Repeat the discussion and compare the class' final results with Euler's theorem.

## Materials

Euler circuit worksheet, scratch paper, colored pencils, Konigsberg overhead, overhead of graphs for experiment with, chalk- or dry-erase board.

## Time

Discussion of the Konigsberg bridge problem: (10 min), group discussion of the Euler circuit worksheet: (15 min.), class discussion of results: (15 min.), group discussion of Euler paths: (10 min.), class discussion of Euler paths (10 min)

## Mathematics Concepts

### Discrete Mathematics Concepts

graph, edge, vertex, circuit, path, Euler circuit, Euler path, degree

### Related Mathematics Concepts

algorithms, theorem, existence

Mathematics as Problem Solving, Mathematics as Communication, Mathematics as Reasoning, Mathematical Connections, Geometry from a Synthetic Perspective, Discrete Mathematics

Algebraic Methods (2), Geometric Techniques (4)

## Further Investigation

1. If an Euler circuit does not exist, what is the minimum number of edges that must be re-traced? (The answer to this involves "Eulerizing a graph", where any odd vertices are turned into even vertices by adding a fictitious edge between two of them. This fictitious edge represents the edges that must be repeated. (See DMTA, Instructors manual, p52.)

When the DMP class worked this activity, many relationships were discovered as a product of looking carefully at various graphs. The group noticed that:
1. No graph can have and odd number of vertices with odd degree.
2. The sum of the degrees of all the vertices must be twice the number of vertices.
3. If a graph has a circuit, then we can start at any vertex. If there's only a path, we must start at one of the two end vertices to follow the path.

It is interesting to note (see Crisler, ex 6, p179) that even with the addition of some newer bridges, the Konigsberg problem remains impossible. Versions of pictures of Konigsberg could include only six bridges (where a path is possible), eight bridges (path is possible), and nine bridges (neither is possible.) (The most common version of the map is the one which appears in Graph Theory:1736-1936, but some copies of this pictures are modified to give them the correct number of bridges.)

## References/Resuorces

Biggs, N., Lloyd E., & Wilson, R. (1976) Graph Theory: 1736 - 1936. Clarendon Press Oxford.

Crisler, N., Fisher, P., & Froelich, G. (1994). Discrete mathematics through applications. New York: W. H. Freeman and Company.

Kenney, M. J., & Hirsch, C. R. (Eds.). (1991). Discrete mathematics across the curriculum, K-12. Reston. VA: National Council of Teachers of Mathematics.

Tucker, A., (1984). Applied Combinatorics. New York: John Wiley & Sons.

Peressini, et al. (1992). Precalculus and Discrete Mathematics. Glenview, Illinois: Scott, Foresman and Company.

Dossey, J., Otto, A., Spence, E., & Vanden Eynden, C. (1993). Discrete Mathematics. Harper Collins College.

McEliece, R., Ash, R., & Ash, C. (1989). Introduction to Discrete Mathematics. New York: Random House.