If the given graph is Eulerian, find an Euler circuit in it. If the graph is not Eulerian,...

If the given graph is Eulerian, find an Euler circuit in it. If the graph is not Eulerian, first Eulerize it and then find an Euler circuit. Write your answer as a sequence of vertices, as we did in Example. There are many possible correct answers to these exercises. We will provide only one in the answer key

Using Fleury’s Algorithm to Find an Efficient Route

Assume you are doing maintenance work along pathways joining locations A, B, and so on in a theme park, as shown in Figure. Find an Euler circuit in this graph to make your job efficient by not retracing pathways. Assume that you leave from and return to building C.

Review the Be Systematic Strategy: If you approach a situation in an organized, systematic way, frequently you will gain insight into the problem.

Graph showing paths in a theme park.

We will use Fleury’s algorithm to find an Euler circuit in this graph.

Step 1: We begin at vertex C and traverse edge CJ, next JK and KI, and then IF. We numbered these edges 1, 2, 3, and 4 in Figure, indicating the order in which we will travel over them. We erase these edges and also vertices J and K because they no longer have any edges joined to them. This gives us the graph in Figure.

Step 2: We are now at vertex F. We cannot traverse FC because it is a bridge. So we traverse FG, GI, IH, and HF (marked 5, 6, 7, and 8), erasing these edges and vertices G, I, and H. The graph now looks like Figure(a).

Step 3: We have no choice now but to traverse FC (edge 9). We follow this with CA and AB (marked 10 and 11). After erasing appropriate edges and vertices, we have the graph in Figure(b).

We can now finish the circuit by traveling over BE, EC, CD, DB, and BC (marked 12, 13, 14, 15, and 16). The final circuit is CJKIFGIHFCABECDBC. Notice that we have traversed every edge exactly once and ended at our starting point, vertex C. If you were to follow this circuit, you would cover each path exactly once in performing maintenance on the paths in the park.