Graph Theory Activity

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

- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Repeat the discussion and compare the class' final results with Euler's theorem.

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

- 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.)

- No graph can have and odd number of vertices with odd degree.
- The sum of the degrees of all the vertices must be twice the number of vertices.
- 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.)

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.