Exam Review Suggestions	
•	Define Euler circuit.
•	Determine whether or not a graph has an Euler circuit. (Use Euler’s Theorem)
•	Eulerize a graph.

Practice Problems
1. Define Euler circuit. 

2. The following picture represents the map of a street, the grey dots representing parking meters. The problem is to walk along each sidewalk that has meters once and only once. 

	a. Draw a graph that represents this problem.
	b. Find an Euler circuit in this graph, or say why one does not exist.
	c. If an Euler circuit does not exist, Eulerize the graph

3. Suppose the edges of a graph represent streets that must be plowed after a snowstorm. In order to Eulerize the graph, four edges must be added. The four added edges represent which of the following?
	a. streets that will not be plowed.
	b. streets that will be traversed twice.
	c. streets that will need to be built.

4. In the graph below, for each of the following paths, determine if it is an Euler circuit. If it is not, explain why not.

a. abcdgfea

	
b. abcdefgdcea

    
c. cbaecdefgd

5. Find a good Eulerization for the following graph.

6.  In the graph shown:                                  

a. Find an Euler Circuit or explain why one doesn’t exist.  (Please clearly indicate any circuit by using vertex labels or numbered edges.)

b. Find a Hamilton circuit, or explain clearly why one doesn’t exist.  (Please clearly indicate any circuit by using numbered or wiggly edges.) 

7. Little Bobby is playing a prank on his parents.  He is planning to rig a bucket of water over every doorway in the house, so that the first person to go through each doorway will get soaked.  The floor plan of his house is shown below.  

Draw a graph which represents this floor plan.  Use one vertex to represent the outside of the house, and one vertex to represent each room of the house.  Connect two vertices with an edge if there is a doorway connecting the areas represented by the vertices.  Label the vertices with the letters used in the floor plan to represent the rooms and the outside.  

Bobby would like to enter the house from the outside, visit each doorway of the house exactly once, and end up outside again.  Use your graph to decide whether or not this is possible.  Explain your answer clearly using graph theory terminology and/or theorems.  If it is possible, give a route that would fulfill his requirements.  If it is not possible, give a route where he revisits doorways as few times as possible.