Suppose a highway inspector needs to inspect the roads in your neighborhood. She needs to travel along every road, but will only need to go once along each. The obvious technique is to model the road system with a graph—in this case, vertices will represent intersections, and every road is shown as an edge—and find an Euler circuit in the graph. The same method can be used if you have to plan a route for a snow plow.

But suppose the graph contains no Euler walk. Then the highway inspector must repeat some edges of the graph in order to return to the starting point. We shall define an Eulerization of a graph G to be a graph, with a closed Euler walk, that is formed from G by duplicating some edges. A good Eulerization is one that contains the minimum number of new edges, and this minimum number is the Eulerization number eu(G) of G. For example, if two adjacent vertices have odd degree, you could add a further edge joining them. This would mean that the inspector must travel the road between them twice.

What if the two odd vertices were not adjacent? One new edge will not suffice— it would be the same as requiring that a new road be built! In most applications this is not feasible.

Sample Problem 1.1 Consider the multigraph G of Fig. 1.1. What is eu(G)?

Find an Eulerization of the road network represented by G that uses the minimum number of edges.

Solution. Look at the multigraph as shown on the left in Fig. 1.2. The black vertices have odd degree, so they need additional edges. As there are four black vertices, at least two new edges are needed; but obviously no two edges will

suffice. However, there are solutions with three added edges—two examples are shown—so eu(G) = 3.

Usually edges have a cost associated with them, and the cost of an Eulerization would equal the sum of the costs of the repeated edges. The problem of finding the cheapest Eulerization is called the Chinese Postman Problem. (The first mathematician to suggest it was Chinese, publishing in a Chinese journal, and he posed it in terms of a postman’s delivery route.)

For our purposes, we shall assume all edges are equal in cost. So we’ll assume that the best Eulerizations are the ones with the fewest added edges.