Page 717 - Discrete Mathematics and Its Applications

696 10 / Graphs

Every vertex in H has even degree (because in G all vertices had even degree, and for each
vertex, pairs of edges incident with this vertex have been deleted to form H). Note that H may
not be connected. Beginning at w, construct a simple path in H by choosing edges as long as
possible, as was done in G. This path must terminate at w. For instance, in Figure 5, c, d, e, c is
a path in H. Next, form a circuit in G by splicing the circuit in H with the original circuit in G
(this can be done because w is one of the vertices in this circuit). When this is done in the graph
in Figure 5, we obtain the circuit a, f, c, d, e, c, b, a.
Continue this process until all edges have been used. (The process must terminate because
there are only a finite number of edges in the graph.) This produces an Euler circuit. The
construction shows that if the vertices of a connected multigraph all have even degree, then the
graph has an Euler circuit.
We summarize these results in Theorem 1.

THEOREM 1 A connected multigraph with at least two vertices has an Euler circuit if and only if each of
its vertices has even degree.

We can now solve the Königsberg bridge problem. Because the multigraph representing
these bridges, shown in Figure 2, has four vertices of odd degree, it does not have an Euler
circuit. There is no way to start at a given point, cross each bridge exactly once, and return to
the starting point.
Algorithm 1 gives the constructive procedure for finding Euler circuits given in the discus-
sion preceding Theorem 1. (Because the circuits in the procedure are chosen arbitrarily, there
is some ambiguity. We will not bother to remove this ambiguity by specifying the steps of the
procedure more precisely.)

ALGORITHM 1 Constructing Euler Circuits.

procedure Euler(G: connected multigraph with all vertices of
even degree)
circuit := a circuit in G beginning at an arbitrarily chosen
vertex with edges successively added to form a path that
returns to this vertex
H := G with the edges of this circuit removed
while H has edges
subcircuit := a circuit in H beginning at a vertex in H that
also is an endpoint of an edge of circuit
H := H with edges of subcircuit and all isolated vertices
removed
circuit := circuit with subcircuit inserted at the appropriate
vertex
return circuit {circuit is an Euler circuit}

Algorithm 1 provides an efficient algorithm for finding Euler circuits in a connected multi-
graph G with all vertices of even degree. We leave it to the reader (Exercise 66) to show that
the worst case complexity of this algorithm is O(m), where m is the number of edges of G.
Example 3 shows how Euler paths and circuits can be used to solve a type of puzzle.