Given the graph below, is it possible to construct a path (or a cycle, i.e. a path starting and ending on the same vertex) which visits each edge exactly once ?
All vertices in a graph for which an Euler circuit exists must have even degree.
Königsberg Bridge Problem
Euler · 1736
The first thing that Euler did was boil the Königsberg problem down to its essentials by stripping away all irrelevant material:
- the shapes and sizes of the land masses don't matter — turn them into points
- all that matters about the bridges is how they connect the land masses — make them into lines connecting the points
- having done that, it is not necessary to actually depict the river to study the problem — leave it out
What results is an abstract representation of Königsberg that depicts just enough (and not a whit more) about the problem to completely describe it. This simplified form makes it easier to study as a mathematical object, and to devise some mathematical theorems about it — which is exactly what Euler did.
The sum of the degrees of all vertices in any graph is twice the number of edges.