In the town of Königsberg (currently called Kaliningrad) there were in the 18-th century seven bridges
which crossed the river Pregel. They connected two islands in the river
with each other and with the opposite banks.
The townsfolk had long amused themselves with this problem:
Is it possible to cross the seven bridges in a continuous walk without recrossing any of them?

The river and the bridges can be represented by the following graph:

The problem was initially solved by the Swiss mathematician
Leonhard Euler (1707 – 1783)

Eulerian tour – a path that contains all edges without repetition.

Eulerian circuit – a path that contains all edges without repetition,
starts and ends in the same vertex.

Eulerian graph – a graph that contains an Eulerian circuit.

Even vertex: a vertex that has an even number of incident edges.

Odd vertex: a vertex that has an odd number of incident edges.

Theorem: G is Eulerian iff G is connected and every vertex is even.

A graph contains an Eulerian tour iff exactly two vertices are odd.
One of them will be the start, the other - the end point in the tour.

It is not possible to go through all the bridges exactly once since there are odd vertices in the corresponding graph.

If a graph is Eulerian, the Eulerian circuit can be found using depth-first search

Eulerian circuit (A, B) (B, E) (E, C) (C, B) (B, D) (D, C) (C, A)

In order to compute the Eulerian circuit, Depth-first search is combined with a method called backtracking