6.1. Euler circuits
The Prussian Königsberg was located on the Pregel River, and included two islands which were connected to each other and the mainland by seven bridges. The citizens permanently attempted to make a walk in the city crossing all bridges once and return to the starting point. Leonard Euler was asked to give a definitive answer to this problem. He proved in 1736 that it is not possible: there is no such a circuit. In fact, he proved more. He gave a general solution for such problems and so, this solution is considered to be the first theorem of graph theory.
Figure 6.1. The seven bridges in Königsberg, and its graph model
We recall that a circuit is a closed trail, while a trail is an alternating sequence of vertices and edges in which no edge is repeated.
A circuit in a graph G containing all the edges is said to be an Euler circuit of G. A graph is Eulerian if it has an Euler circuit. An Euler trail contains all edges but it is not closed.
A graph G is defined to be even (odd) graph if all its vertices have even (odd) degree.
Theorem 6.1. A non-trivial connected graph has an Euler circuit iff each vertex has even degree.
Proof.
-
Let be an Euler
circuit in G. If
occurs
k times in the sequence
, then
.
- Let us suppose that each vertex has even degree in G. We will prove by induction on the number of edges.
If there are no edges, then there is nothing to prove, so we we proceed the induction step.
Since then G
contains a cycle. (see the Theorem 3.7.)
Let C be a circuit in G with the maximal number of edges, and suppose C is not Eulerian, i.e. it does not contain all edges.
As G
is connected, C contains a vertex x which is in a non-trivial
component H of .

Every vertex of H has even degree in H, so by the induction hypothesis H contains an Euler circuit. We denote this circuit by D.
C and D are edge-disjoint and they have at least one common vertex. C and D can be combine to form a circuit with more edges than C. This would be a contradiction, since C was maximal.
Theorem 6.2. A connected graph has an Euler
trail from a vertex x to a vertex iff x
and y are the only vertices of odd degree.
Proof.
- The condition is clearly necessary.
-
Suppose that x and y
are the only vertices of odd degree. Let be obtained
from G by adding to it a vertex u together with the edges ux
and uy.
By the Theorem 6.1. has an Euler
circuit
. Clearly,
is an Euler
trail from x to y.