1.	On a graph that represents six cities and the roads between them, the valence of vertex A is 4.  What does this mean in real world terms? 	

2.	A graph that represents six cities and the roads between them is not connected.  What does this mean in real world terms? 	

3.	Draw a graph representing four cities A, B, C, and D with a road that connects each pair of cities given:
AB, AC, BC, BD, CD	

4.	Draw a graph with vertices A, B, C, and D in which the valence of vertices A and D is 3 and the valence of vertices B and C is 2.	

5.	Draw a graph with vertices A, B, C, and D in which the valence of each vertex is 3.	

6.	Consider the path represented by the sequence of numbered edges on the graph below.  Explain why the path is not an Euler circuit.

7.	Consider the path represented by the sequence of numbered edges on the graph below.  Explain why the path is not an Euler circuit.

8.	Draw a graph with 8 vertices, with the valence of each vertex even, that does not have an Euler circuit.	

9.	Explain why the graph shown below does not have an Euler circuit.

10.	Explain why the graph shown below does not have an Euler circuit.

Use the following to answer questions 11-14:

Identify an Euler circuit on the graphs below by numbering the sequence of edges in the order traveled.

11.	 

12.	

13.	

14.	

Use the following to answer questions 15-18:

Add wiggly edges to find an efficient Eulerization of the graphs shown below.

15.	

16.	

17.	

18.	

19.	The map below gives the territory of a parking control officer.  The dots represent meters that must be checked.  Draw the graph that would be useful for finding an efficient route.

20.	For the street network shown below, draw a graph that would be useful for routing a garbage truck. Assume all streets are two way and that passing once down the street is sufficient for collecting trash from both sides.

21.	Find an Euler circuit on the graph on the left and use it to find a circuit on the graph on the right that reuses one edge.

22.	Find an Euler circuit on the graph on the left and use it to find a circuit on the graph on the right that reuses 4 edges.

23.	Find an Euler circuit on the graph on the left and use it to find a circuit on the graph on the right that reuses 3 edges.

24.	Why would a city street department want its snow plow operator's path to follow an Euler circuit if possible? 	

25.	Give three real world applications in which a worker would want to find an Euler circuit on a street network.	

26.	Draw a connected graph with 7 vertices where each vertex has valence 4.	

27.	Draw a graph with 6 vertices where the valences are 1, 2, 2, 3, 4, and 4.	

28.	Find an eulerization with 9 added edges for a 3-by-6 block rectangular street network.	

29.	Draw a graph where every vertex has a valence of at least 2, but removing a single edge disconnects the graph.	

30.	Draw a graph with 5 vertices where the valence of each vertex is 4.	

Answer Key

1.	If the valence of vertex A is four, it means there are four roads which lead to town A.	
2.	If the graph that represents six cities and the roads between them is not connected, it means that it is not possible to travel between all cities.  More specifically, it means at least one pair of cities has no connecting path of roads.	
3.	
	
4.	
	
5.	
	
6.	The path is not an Euler circuit because it does not start and stop at the same vertex.	
7.	The path is not an Euler circuit because it does not cover every edge of the graph.	
8.	Answers may vary.  One solution is:

9.	The graph does not have an Euler circuit because the valences of vertex B and vertex D are odd.	
10.	The graph does not have an Euler circuit because it is not connected.	
11.	Answers may vary.  One solution is:

12.	Answers may vary.  One solution is:

13.	Answers may vary.  One solution is:

14.	Answers may vary.  One solution is:

15.	Answers may vary.  One solution is:

16.	Answers may vary.  One solution is:

17.	Answers may vary.  One solution is:

18.	Answers may vary.  One solution is:

19.	
	
20.	
	
21.	Answers may vary.  One solution is:

22.	Answers may vary.  One solution is:

23.	Answers may vary.	
24.	If the snow plow operator followed an Euler circuit, he would end his route at the city garage where he started.  Also, no time or gas would be wasted traveling down streets that were already plowed.	
25.	Answers may vary.  Some situations include:
Plowing snow
Painting lines down the center of streets
Trash collection
Checking gutters on the corners of all streets
Checking parking meters along the edge of all streets
Delivering mail to all houses on all streets	
26.	Answers will vary. One solution is:
	
27.	Answers will vary. One solution is:
	
28.	
	
29.	Answers will vary. One solution is:
	
30.	Answers will vary. One solution is: