Mathematics 357 – Combinatorics Discussion 4 – Euleriana April 8, 2005

Background

Last time we introduced a number of concepts and terms dealing with simple and general graphs. Here is an additional one. A trail in a graph is a walk with distinct edges. (You can visit the same vertex several times, though. That’s what makes a trail different from a path.) Today, we will use this to study what are called Euler trails and Euler circuits.

Discussion Questions

A) (a “warm-up”) Recall that the degree of a vertex v in a graph G = (V, E) is the number of edges with v as one endpoint. What happens if you add up the degrees of all the vertices in a (simple or general) graph? Try some examples. What is always true about the sum? Prove your claim.

The beginnings of graph theory can be traced back to an article published by the Swiss mathematician Leonhard Euler in 1736. In this article, Euler considered the so-called “Bridges of Königsberg” problem. The city of Königsberg (in what is now Poland) was located on two islands and two banks of a river with bridges in the arrangement given in the diagram on the left below:

The question was: Is it possible to take a walk through the city so that you cross each bridge exactly once? Euler’s first innovation was replacing the actual map of the city by an equivalent graph, shown in the diagram on the right above. The vertices V correspond to the different “land masses” (the two islands and the two banks of the river) and the edges represent the bridges.

B) By considering the Königsberg graph, Euler found that there is no way to take a walk through the city crossing each bridge exactly once. Why not? (Explain what goes wrong.)

C) Now, let’s ask the same question for an arbitrary connected simple graph: Under what conditions should it be possible to find a trail that uses each edge in the graph exactly once?

Thinking as in C, formulate a necessary condition. What must happen at each vertex in a graph if you can find a path that uses each edge exactly once? What happens if the trail starts and ends at different points?

D) If you have the right necessary conditions in part C, then they also turn out to be sufficient. Can you prove this? You can either

• try to develop your own proof by saying how to construct an Euler trail if your conditions are satisfied, or

• look at Theorems 11.2.2 and 11.2.3 in the text, Read those and write up the arguments in your own words, filling in any details that are not clear to you, and illustrating the arguments with appropriate diagrams.

Assignment

Group writeups due in class Wednesday, April 13.