Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 36 · Getting Started

The Seven Bridges of Königsberg

Follow the puzzle that started graph theory: Euler's solution to the Königsberg bridges, Euler paths and circuits, and a Python check that proves no walk crosses each bridge once.

In the 1700s the city of Königsberg (today Kaliningrad) had four land areas separated by a river, joined by seven bridges. Citizens wondered: can you take a walk that crosses every bridge exactly once? Nobody found one. In 1736 Leonhard Euler explained why no such walk exists, and in doing so he invented graph theory.

His key idea was to forget the map. Only two facts matter: which land areas exist and which bridges join them. Land areas become vertices and bridges become edges. Because two areas are joined by two bridges, the result is a multigraph.

graph TD
  A["North bank (A)"] --- C["Island (C)"]
  A --- C
  A --- D["East bank (D)"]
  B["South bank (B)"] --- C
  B --- C
  B --- D
  C --- D

Seven edges. Vertex degrees: A = 3, B = 3, C = 5, D = 3.

Euler trails and circuits

A trail is a walk that never repeats an edge. An Euler trail (or Euler path) uses every edge exactly once. An Euler circuit is an Euler trail that ends where it began.

Euler's reasoning is short and beautiful. Imagine walking along such a trail:

  • Each time you pass through a vertex, you use one edge to enter and one to leave: two edges.
  • So every vertex in the middle of the walk uses an even number of edges.
  • Only the start and end vertices can have an odd number of edges, because the start has an extra departure and the end an extra arrival.

If the start and end are the same vertex (a circuit), every vertex has even degree.

Euler's theorem

For a graph (multigraphs allowed) in which all edges lie in one connected piece:

  1. It has an Euler circuit if and only if every vertex has even degree.
  2. It has an Euler trail that is not a circuit if and only if exactly two vertices have odd degree. The trail must start at one of them and end at the other.
  3. With more than two odd vertices, neither exists.

Königsberg has four odd vertices (degrees 3, 3, 5, 3), so no walk crosses every bridge exactly once. Puzzle solved, 289 years ago, without trying a single route.

Python Does Königsberg have an Euler trail?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A general checker

The theorem becomes a tiny algorithm. We must also check that the edges are connected, otherwise two separate loops would pass the "all even" test but cannot be traced in one walk. We use a simple union-find on the vertices that have edges.

Python Euler trail / circuit checker

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two-triangle graph shows why connectivity matters. The bowtie (two triangles sharing the vertex 3) has all even degrees and is connected, so it has an Euler circuit.

Finding the trail itself: Hierholzer's idea

The theorem says whether a trail exists. To find one, Hierholzer's algorithm repeatedly follows unused edges until it is stuck (which can only happen back at the start), then splices in extra loops. Here is a compact version for a graph with all even degrees:

Python Hierholzer's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The algorithm runs in time proportional to the number of edges. Notice the lesson Euler taught the world: model first, then reason about the structure instead of searching blindly.

Common mistakes

  • Counting vertices of odd degree but forgetting the connectivity requirement.
  • Mixing up Euler trails (every edge once) with Hamilton paths (every vertex once). The first is easy to decide; the second is famously hard.
  • Allowing a "bridge" to be crossed by walking half-way: edges are used whole.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A connected graph has exactly two vertices of odd degree. Which statement is true?

    Exactly two odd vertices means an open Euler trail exists, and it must start at one of them and end at the other.
  2. 2. Why does Königsberg have no walk crossing each bridge exactly once?

    The land areas have degrees 3, 3, 5 and 3: four odd vertices, more than the two an Euler trail can tolerate.
  3. 3. A connected graph has an Euler circuit if and only if:

    Even degree everywhere lets every visit to a vertex use one edge in and one edge out.
  4. 4. An Euler trail uses every ___ exactly once.

    Euler trails cover every edge once. Visiting every vertex once is a Hamilton path, a different problem.

Summary

  • Euler modeled Königsberg as a multigraph and founded graph theory.
  • An Euler trail uses every edge once; an Euler circuit also returns to the start.
  • A connected graph has an Euler circuit iff all degrees are even, and an open Euler trail iff exactly two are odd.
  • Königsberg has four odd vertices, so the walk is impossible.
  • Hierholzer's algorithm finds an Euler circuit in linear time.

Next: The Adjacency Matrix