EXAMPLE 4 A Better Eulerization

In Figure 1.16a, we begin with the same graph as in Figure 1.14, but we eulerize it in a different way—by adding only one edge (see Figure 1.16b). Figure 1.16c shows an Euler circuit on the eulerized graph, and in Figure 1.14d we see how it is squeezed onto the original graph. There is only one reuse of an edge, because we added one edge during eulerization.