Königsberg Bridge Problem

May 3, 2001

Definitions vertex – a point (where edges meet). edge – a line that joins two vertices. degree – the degree of a vertex is the number of edges that come out of (or go into) that

vertex. graph – something with vertices (plural of vertex) and edges. path – a sequence of vertices that are joined by edges.

Really, I should say … a path is a sequence of edges that link up nicely, i.e. if we represent an edge e as a pair of vertices (v, w) where we think of v as the starting vertex of the

edge and w as the end vertex of the edge then a path is a sequence of the form

(v_{1}, v_{2}), (v_{2}, v_{3}), … (where the end vertex of one edge is the starting vertex of the next edge). If you can’t see the difference … it probably won’t matter.

connected – a graph is connected iff between every pair of vertices there is a path. circuit – a path which begins and ends at the same vertex. Euler circuit – a circuit which uses up every edge of a graph. Euler path – a path which uses up every edge of a graph (the starting vertex and the end

vertex of the path need not be the same). loop – an edge which begins and ends at the same vertex. Theorem 1. Let Γ be a connected graph. Then Γ has an Euler circuit if and only if all vertices are of even degree. Proof. ‘ ⟹ ’ Observe that:

• if we start at a vertex v and move away via some edge and continue along some path through other vertices and then move back to the starting vertex v via some edge (different from the away edge) then the away-edge and the to-edge contribute 2 to the degree of the vertex v;

• if we pass through a vertex v, i.e. move to v via some edge and then move away from v via another edge then the to-edge and the away-edge contribute 2 to the degree of the vertex v.

Now suppose Γ has an Euler circuit. Then such a circuit starts and ends at the same vertex and uses up every edge. Hence for any vertex v we either start and end at v and pass through v a total of (say) k times in which case the degree of v is 2 + 2k; or we pass through v some number of times, k say, without starting and ending at v, in which case the degree of v is 2k. In either case the degree of v is even. ‘ ⟸ ’ Now suppose each vertex of Γ has even degree. If Γ has only one vertex then it consists of that vertex and a number of loops. The desired Euler circuit is obtained by traversing each of the loops in some order.

Now consider the case where Γ has more than one vertex. Create a copy Γ′ of Γ in the following way. Initially Γ′ has all the vertices of Γ but no edges. Choose any vertex v_{0} of Γ. Take any edge, (v_{0}, v_{1}) say, out of v_{0}. Delete it from Γ and add it to Γ′. If v_{1} ≠ v_{0} then the modified graph Γ now has two vertices of odd degree, namely v_{0} and v_{1}, in which case there is another edge leaving v_{1}, (v_{1}, v_{2}) say. Delete (v_{1}, v_{2}) from Γ and add it to Γ′. Continue deleting edges (v_{k−1}, v_{k}) from Γ and adding them to Γ′ until v_{k} = v_{0}. (This is possible since at each stage the vertex v_{k−1} will be of odd degree; and the process must terminate as there are only a finite number of edges.) What we have done is: we have found a circuit

(v_{0}, v_{1}), (v_{1}, v_{2}), …, (v_{k−1}, v_{k})

in the original Γ, deleted it from Γ and added it to Γ′. At this stage Γ′ consists of a circuit and Γ is now, once again, a graph all of whose vertices are of even degree (though now it may no longer be connected).

Take one of the connected pieces remaining in Γ. Call it Δ. One of the vertices of Δ must belong to Γ′ (otherwise the original Γ would not have been connected). Suppose this vertex is v_{i}. Now find a circuit in Δ starting and finishing at v_{i} (in the same way as above),

(v_{i}, w_{1}), (w_{1}, w_{2}), …, (w_{ℓ−1}, w_{ℓ})

say, where w_{ℓ} = v_{i}; delete it from Γ and add it to Γ′. Note that Γ′ now consists of the Euler circuit

(v_{0}, v_{1}), (v_{1}, v_{2}), …, (v_{i−1}, v_{i}), (v_{i}, w_{1}), (w_{1}, w_{2}), …, (w_{ℓ−1}, v_{i}), (v_{i}, v_{i+1}), …, (v_{k−1}, v_{k}).

We keep performing the last step until we have used up every edge of Γ. We are guaranteed of succeeding, since after each step Γ consists of connected pieces all of whose vertices are of even degree and Γ′ consists of an Euler circuit; and we must eventually run out of edges.

Theorem 2. Let Γ be a connected graph. Then Γ has an Euler path if and only if Γ has either 0 or 2 vertices of odd degree.

Proof. ‘ ⟹ ’ Suppose Γ has an Euler path P beginning at v and ending at w. If v = w then the Euler path P is also an Euler circuit and thence (by the previous theorem) all vertices are of even degree (that is, there are 0 vertices of odd degree). Otherwise v ≠ w and we can create a new graph Γ′ from Γ by adding the edge (w, v) to Γ, and an Euler circuit P′ from P by adding (w, v) to P. Now P′ is an Euler circuit for Γ′ and so by the previous theorem all vertices of Γ′ have even degree. Deleting the edge (w, v) again from both Γ′ and P′, restores Γ and P, and in so doing we find that both w and v (and no other vertex) have odd degree (that is, there are 2 vertices of odd degree).

‘ ⟸ ’ Now suppose there are 0 or 2 vertices of Γ of odd degree. If Γ has 0 vertices of odd degree then Γ has an Euler circuit (and hence an Euler path) by the previous theorem. On the other hand, if Γ has 2 vertices v, w of odd degree then Γ, create a new graph Γ′ from Γ by adding the edge (w, v) to Γ. Then Γ′ is a connected graph such that all its vertices are of even degree. By the previous theorem, Γ′ has an Euler circuit P′. By changing the starting vertex of P′ if necessary (and if necessary the direction in which we traverse P′) we can arrange that the edge (w, v) is the last edge of the path P′. That is, P′ is of the form

P, (w, v)

for some path P, and P is an Euler path of the graph Γ.

The Königsberg bridge problem

In the town of Königsberg in the 18th century there were seven bridges across the river Pregel. They connected two islands in the river with each other and with opposite banks (more precisely: there was one bridge connecting the two islands, one island had two bridges to each bank, and the other island had just one bridge to each bank). The townsfolk had long amused themselves with the problem:

Is it possible to cross the seven bridges in a continuous walk without recrossing any of them?

The problem is equivalent to determining whether there is an Euler path for the graph where each bridge is represented by an edge of the graph and the islands and banks of the river Pregel are represented by vertices of the graph. This gives a graph of four vertices A, B, C and D, say, where A and D represent the banks and B and C represent the islands, such that between A and B there are two edges, between B and C there are also two edges, and between each of the pairs of vertices A and D, B and D, and C and D, there is one edge.

Solution

Each of the vertices A, B, C and D has odd degree. That is, there are 4 vertices with odd degree. By the second theorem, no Euler path exists. Thus the answer is: No, it is not possible to cross the seven bridges in a continuous walk without recrossing any of them.

Follow-up Exercise

Sometime later an eighth bridge was constructed directly connecting the two banks of the river Pregel. Show that it is now possible to find an Euler path across the bridges, and find such a path. In so doing, state what vertices must be chosen as start and finish points and explain why. See if you can demonstrate the ‘ ⟸ ’ part of the proof of Theorem 1 in constructing your path. (To do this you have to add an edge! For Theorem 1, all vertices should be of even degree. Check the idea in Theorem 2.)