38 Euler paths and Euler cycles
In the normal definition of a path, there’s no restriction on the number of times we can use an edge or how many times we can pass through a vertex.
The kind of path that arises from the restriction in the Königsberg bridge problem has been called “An Euler Path” (after Euler). So we can summarise the following definitions:
- An Euler path is a path where every edge of the graph is used exactly once.
- An Euler cycle (or sometimes Euler circuit) is an Euler Path that starts and finishes at the same vertex.
Euler paths and Euler circuits have no restriction on the number of times a node can be used, e.g. in the bridges problem it was no problem that we pass through the central region any number of times (in fact, we need to in order to cross all the bridges), however there is also a special path called a “Hamiltonian path” which instead has the restriction that we can pass through each vertex only once: for example, if you were to describe a sequence of trips around Australia where you visit each of the capital cities only once.
We’ll now consider Euler’s solution to the Königsberg bridge problem and the theorem that allows us to solve any similar problem involving graphs.
The following video gives some examples for finding Euler paths.
Explain it in your own words
Give a description of the Königsberg bridge problem (include a diagram) and your own explanation of why it’s not solvable so that someone who’d never studied it before could understand. If there are things you don’t remember, go back over the notes and consolidate your description, simplifying the language wherever possible.
