EXAMPLE 2 Finding an Euler Circuit

Check the valences of the vertices and the connectivity of the graph in Figure 1.8a to verify that the graph does have an Euler circuit. Now try to find an Euler circuit for that graph. You can start at any vertex. When you are done, compare your solution with the Euler circuit given in Figure 1.8b. If your path covers each edge exactly once and returns to its original vertex (which is a circuit), then it is an Euler circuit, even if it is not the same as the one we give.