Chapter 14.2, Problem 41E

Exercises 37-44 are based on the following theorem.

1. If a graph has an Euler path that begins and ends at different vertices, then these two vertices are the only vertices with odd degree. (All the rest have even degree.)

If exactly two vertices in a connected graph have odd degree, then the graph has an Euler path beginning at one of these vertices and ending at the other.

In Exercises 37-40, determine whether the graph has an Euler path that begins and ends at different vertices. Justify your answer. If the graph has such a path, say at which vertices the path must begin and end.

Floor PlansIn Exercises 41-43, refer to the floor plan indicated, and determine whether it is possible to start in one of the rooms of the building, walk through each door exactly once, and end up in a different room from the one you started in. Justify each answer.

Refer to the floor plan shown in Exercise 34.