Question

Hall Dining Dining Room Bedroom Kitchen Den

Using Euler’s Path Theorem

Use the house plan below to determine whether there is a path through these rooms that goes through every doorway exactly once.

. Use a separate answer sheet:

Step 1: Make a graph separate from the drawing.

a. Each room should be a vertex. Each door corresponds to an edge. (If there are two doors that lead from one room, there should be two edges leaving that vertex; every door should be represented by an edge.)

b. Each vertex should be labeled. Use the first letter of each room name to designate the vertex (ex: “D” for Den, “DR” for Dining Room, or any other appropriate label [“E” for eat?]).

c. Write the degree of each vertex next to it.

Step 2: Complete the following

a. If there is a path through the rooms that goes through every doorway exactly once, state what the path would be by describing the vertices in the correct order.

b. Explain how you know whether or not there is a path using Euler’s path theorem.

c. Is there a path through the rooms that goes through every doorway exactly once and back to the room in which you started? Explain how you know, using Euler’s circuit theorem.