Seven Bridges of Königsberg

Example

The city of Königsberg had four land areas, joined by seven bridges over the river Pregel. The problem asked for a walk that crosses each bridge exactly once.

Model each land area as a vertex and each bridge as an edge. This gives a connected multigraph with $4$ vertices and $7$ edges. The degrees of the vertices are $5$, $3$, $3$ and $3$. An Eulerian trail can have at most two vertices of odd degree, by the theorem on degrees along an Eulerian trail. Here all four degrees are odd, so the walk does not exist.