The Art and Craft of Problem Solving

114 CHAPTER^4 THREE IMPORTANT CROSSOVER TACTICS

Therefore if a graph has an Eulerian path, it must have either zero or exactly two odd­

degree vertices. In fact, this is a necessary and sufficient condition. More precisely,

A connected graph (or multigraph^5 ) possesses an Eulerian path if and

only if it has zero or exactly two odd-degree vertices. In the fo rmer

case, the path is a closed path. In the latter, the path must begin and

end at the odd-degree vertices.

It is possible to prove this by induction, and indeed, the argument below can easily

be rewritten as an induction proof. But it is much more instructive to present a new

type of argument, an algorithmic proof, in which we give a general recipe for the

construction of an Eulerian path.

Consider first a graph with exactly two odd-degree vertices, which we will call

sand f. Let us try to naively draw an Eulerian path, starting from s. We will travel

randomly, figuring that we can't lose: if we enter an even-degree vertex, we can then

leave it, and either this vertex will have no untraveled edges left or an even number of

them, in which case we can travel through later.

But this doesn't quite work. Consider the following graph (actually, it is a multi­

graph, but we will just use the term "graph" for now; there shouldn't be any confusion).

The edges are labeled with upper-case letters, and vertices are labeled with lower-case

letters.

c

B

S .... ---,-A-..... f

H

G

L

Starting at vertex s, what if we traversed, in order, edges A,B,C,D,E,F,G,H? We

would be stuck at vertex f, with no way to "backtrack" and traverse the other edges. In

this case, let us temporarily remove the edges that we have traveled. We are left with

the subgraph containing the edges I,J,K, L. This subgraph has four vertices, each

with even degree. Since the original graph was connected, the subgraph "intersected"

some of the edges that we removed, for example, at the vertex labeled u. Now let

us apply the "naive" algorithm to the subgraph, starting at u. We traverse, in order,

J, K,L,I. We ended up back at u, and that is no coincidence. Since all the vertex

degrees of our subgraph are even, we cannot get stuck unless we return to our starting

point.

So now we can perform "reconstructive surgery" on our original path and get an

Eulerian path for the entire graph.

5 As mentioned earlier, we assume that graphs are not multigraphs. When investigating Eulerian paths, multi­

graphs may be relevant, but this is virtually the only place in this text where they are.