Examples of Logic Lessons in 5th Grade
Graph Theory. 7 Bridges of Konigsberg. Euler's circuit
What is a Chromatic Number for the following graphs?
7 Bridges of Konigsberg
In the 1700s, there was a city named Konigsberg in East Prussia (it is now Kaliningrad, Russia). The Pregel River runs through Konigsberg, and it is split between two branches. There were 7 bridges in the city, connecting the riverbanks and the islands, as shown to the left.
Is it possible for the person to take a walk through the city, crossing each bridge exactly once, and finishing at the starting point?
1. Try to solve this problem. It may be helpful to use the simplified picture of the city shown lower left.
Do you think that a person can walk through the city, crossing every bridge exactly 1 time, and start and end at the same point?
The mathematician Leonhard Euler answered this question with graph theory! He drew a graph with the regions A, B, C, and D as vertices and the bridges as edges. It looks like this.
2. Find the degree of every vertex of the graph that represents Konigsberg.
Any path that traces the graph by going across each edge exactly once and starts and ends at the same point is called an Euler circuit.
3. Explain why finding an answer to the Bridges of Koenigsburg problem is the same as finding an Euler circuit on the graph shown.
Euler showed that if there is any vertex of the graph that has odd degree, then the graph does not have an Euler circuit. He also showed that if all of the vertices of the edges have an even degree, then the graph does have an Euler circuit.
This graph has an Euler circuit, because all of the vertices have even degree. You can find the circuit by traveling along the graph in this order: A → B →D →C →B →A.
(Notice that vertex B is used twice. This is fine in an Euler circuit.)
4. Does the graph showing the Konigsberg bridges have an Euler circuit? Why or why not?
5. For each of the graphs shown below, decide if they have an Euler circuit. If they do, find an Euler circuit. If it doesn't have an Euler circuit, explain why not.
6. For the graphs in problem 5 that have Euler circuits, compare your Euler circuit to a classmate's Euler circuit. Do you have the same circuits?