CHAP. 8] GRAPH THEORY 161
Fig. 8-10We now show how Euler proved that the multigraph in Fig. 8-10(b)is not traversable and hence that the
walk in Königsberg is impossible. Recall first that a vertex is even or odd according as its degree is an even or an
odd number. Suppose a multigraph is traversable and that a traversable trail does not begin or end at a vertexP.
We claim thatPis an even vertex. For whenever the traversable trail entersPby an edge, there must always
be an edge not previously used by which the trail can leaveP. Thus the edges in the trail incident withPmust
appear in pairs, and soPis an even vertex. Therefore if a vertexQis odd, the traversable trail must begin or
end atQ. Consequently, a multigraph with more than two odd vertices cannot be traversable. Observe that the
multigraph corresponding to the Königsberg bridge problem has four odd vertices. Thus one cannot walk through
Königsberg so that each bridge is crossed exactly once.
Euler actually proved the converse of the above statement, which is contained in the following theorem and
corollary. (The theorem is proved in Problem 8.9.) A graphGis called anEuleriangraph if there exists a closed
traversable trail, called anEuleriantrail.
Theorem 8.3 (Euler):A finite connected graph is Eulerian if and only if each vertex has even degree.
Corollary 8.4: Any finite connected graph with two odd vertices is traversable. A traversable trail may begin at
either odd vertex and will end at the other odd vertex.
Hamiltonian Graphs
The above discussion of Eulerian graphs emphasized traveling edges; here we concentrate on visiting vertices.
AHamiltonian circuitin a graphG, named after the nineteenth-century Irish mathematician William Hamilton
(1803–1865), is a closed path that visits every vertex inGexactly once. (Such a closed path must be a cycle.) If
Gdoes admit a Hamiltonian circuit, thenGis called aHamiltonian graph. Note that an Eulerian circuit traverses
every edge exactly once, but may repeat vertices, while a Hamiltonian circuit visits each vertex exactly once
but may repeat edges. Figure 8-11 gives an example of a graph which is Hamiltonian but not Eulerian, and vice
versa.
Fig. 8-11