Page 716 - Discrete Mathematics and Its Applications

10.5 Euler and Hamilton Paths 695

a b

c d c d
f

e e
G H
FIGURE 5 Constructing an Euler Circuit in G.

Suppose that G is a connected multigraph with at least two vertices and the degree of
every vertex of G is even. We will form a simple circuit that begins at an arbitrary vertex a
of G, building it edge by edge. Let x 0 = a. First, we arbitrarily choose an edge {x 0 ,x 1 } inci-
dent with a which is possible because G is connected. We continue by building a simple path
{x 0 ,x 1 }, {x 1 ,x 2 },..., {x n−1 ,x n }, successively adding edges one by one to the path until we
cannot add another edge to the path. This happens when we reach a vertex for which we have
already included all edges incident with that vertex in the path. For instance, in the graph G in
Figure 5 we begin at a and choose in succession the edges {a, f }, {f, c}, {c, b}, and {b, a}.
The path we have constructed must terminate because the graph has a finite number of
edges, so we are guaranteed to eventually reach a vertex for which no edges are available to add
to the path. The path begins at a with an edge of the form {a, x}, and we now show that it must
terminate at a with an edge of the form {y, a}. To see that the path must terminate at a, note that
each time the path goes through a vertex with even degree, it uses only one edge to enter this
vertex, so because the degree must be at least two, at least one edge remains for the path to leave
the vertex. Furthermore, every time we enter and leave a vertex of even degree, there are an even
number of edges incident with this vertex that we have not yet used in our path. Consequently,
as we form the path, every time we enter a vertex other than a, we can leave it. This means that
the path can end only at a. Next, note that the path we have constructed may use all the edges
of the graph, or it may not if we have returned to a for the last time before using all the edges.
An Euler circuit has been constructed if all the edges have been used. Otherwise, consider
the subgraph H obtained from G by deleting the edges already used and vertices that are not
incident with any remaining edges. When we delete the circuit a, f, c, b, a from the graph in
Figure 5, we obtain the subgraph labeled as H.
Because G is connected, H has at least one vertex in common with the circuit that has been
deleted. Let w be such a vertex. (In our example, c is the vertex.)

LEONHARD EULER (1707–1783) Leonhard Euler was the son of a Calvinist minister from the vicinity of
Basel, Switzerland. At 13 he entered the University of Basel, pursuing a career in theology, as his father wished.
At the university Euler was tutored by Johann Bernoulli of the famous Bernoulli family of mathematicians.
His interest and skills led him to abandon his theological studies and take up mathematics. Euler obtained his
master’s degree in philosophy at the age of 16. In 1727 Peter the Great invited him to join the Academy at
St. Petersburg. In 1741 he moved to the Berlin Academy, where he stayed until 1766. He then returned to St.
Petersburg, where he remained for the rest of his life.
Euler was incredibly prolific, contributing to many areas of mathematics, including number theory, com-
binatorics, and analysis, as well as its applications to such areas as music and naval architecture. He wrote
over 1100 books and papers and left so much unpublished work that it took 47 years after he died for all his work to be published.
During his life his papers accumulated so quickly that he kept a large pile of articles awaiting publication. The Berlin Academy
published the papers on top of this pile so later results were often published before results they depended on or superseded. Euler
had 13 children and was able to continue his work while a child or two bounced on his knees. He was blind for the last 17 years of
his life, but because of his fantastic memory this did not diminish his mathematical output. The project of publishing his collected
works, undertaken by the Swiss Society of Natural Science, is ongoing and will require more than 75 volumes.