EXAMPLE 3 Eulerizing a Graph

Suppose we want to eulerize the graph of Figure 1.14a. When we eulerize a graph, we first locate the vertices with odd valence. The graph in Figure 1.14a has two, B and C. Next, we add one end of an edge at each such vertex, matching up the new edge with an existing edge in the original graph. Figure 1.14b shows one way to eulerize the graph. Note that B and C have even valence in the second graph. After eulerization, each vertex has even valence. To see an Euler circuit on the eulerized graph in Figure 1.14c, simply follow the edges in numerical order and in the direction of the arrows, beginning and ending at vertex A. The final step, shown in Figure 1.14d, is to “squeeze” our Euler circuit onto the original graph. There are two reuses of previously covered edges. Notice that each reuse of an edge corresponds to an added edge.