1.	What is the valence of vertex A in the graph below?

	A)  2    B)  3    C)  4    D)  5	

2.	What is the valence of vertex A in the graph below?

	A)  3    B)  5    C)  7    D)  11	

3.	What is the valence of vertex A in the graph below?

	A)  3    B)  4    C)  5    D)  6	

4.	What is the valence of vertex A in the graph below?

	A)  3    B)  4    C)  5    D)  6	

5.	Which of the following defines the valence of vertex A of a graph?	
A)	The total number of vertices of the graph	
B)	The number of edges meeting at vertex A	
C)	The total number of edges of the graph	
D)	None of the above	

6.	The valence of vertex A in the graph shown below is 1.

	A)  true    B)  false	

7.	Which of the graphs below are connected?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

8.	Which of the graphs below are connected?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

9.	Which of the graphs below are connected?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

10.	Which of the following statements about a connected graph is always true?	
A)	Every pair of vertices is joined by a single edge.	
B)	A path of edges exists between any two vertices of the graph.	
C)	There are an even number of vertices on the graph.	
D)	There are an even number of edges on the graph.	

11.	A graph that is not connected must have at least one vertex with valence 0.	
	A)  True    B)  False	

12.	If a graph of four vertices has a vertex with valence 0, then the graph is not connected.	
	A)  True    B)  False	

13.	If a graph of six vertices has only four edges it is not connected.	
	A)  True    B)  False	

14.	Which of the graphs below have Euler circuits?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

15.	Which of the graphs below have Euler circuits?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

16.	Which of the graphs below have Euler circuits?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

17.	Which of the graphs below have Euler circuits?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

18.	Every graph with an Euler circuit has an even number of vertices.	
	A)  True    B)  False	

19.	Every graph with an Euler circuit has an even number of edges.	
	A)  True    B)  False	

20.	Every graph that has an Euler circuit is connected.	
	A)  True    B)  False	

21.	Every connected graph has an Euler circuit.	
	A)  True    B)  False	

22.	Every graph with an Euler circuit has only vertices with even valences.	
	A)  True    B)  False	

23.	It is possible for a graph with all vertices of even valence to not have an Euler circuit.	
	A)  True    B)  False	

24.	Consider the paths represented by the numbered sequence of edges on the graphs below.  Which path represents an Euler circuit?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

25.	Consider the paths represented by the numbered sequence of edges on the graphs below.  Which path represents an Euler circuit?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

26.	Consider the paths represented by the numbered sequence of edges on the graphs below.  Which path represents an Euler circuit?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

27.	Consider the path represented by the sequence of numbered edges on the graph below.  Why does the path not represent an Euler circuit?

A)	The path does not start and stop at the same vertex.	
B)	The path does not cover every edge of the graph.	
C)	The path uses some edges more than one time.	
D)	The path does not touch each vertex of the graph.	

28.	Consider the path represented by the sequence of numbered edges on the graph below.  Why does the path not represent an Euler circuit?

A)	The path does not start and stop at the same vertex.	
B)	The path does not cover every edge of the graph.	
C)	The path uses some edges more than one time.	
D)	The path does not touch each vertex of the graph.	

29.	Consider the path represented by the numbered sequence of edges of the graph below.  Which statement is true?

A)	The path is not a circuit.	
B)	The path is an Euler circuit.	
C)	The path is a circuit, but not an Euler circuit.	
D)	None of the above	

30.	Consider the path represented by the numbered sequence of edges on the graph below.  Which statement is true?

A)	The path is not a circuit.	
B)	The path is an Euler circuit.	
C)	The path is a circuit, but not an Euler circuit.	
D)	None of the above	

31.	Consider the path represented by the numbered sequence of edges on the graph below.  Which statement is true?

A)	The path is not a circuit.	
B)	The path is an Euler circuit.	
C)	The path is a circuit, but not an Euler circuit.	
D)	None of the above	

32.	For which of the two situations below is it desirable to find an Euler circuit or an efficient eulerization of a graph?
I. A pizza delivery person takes pizzas to ten houses in a neighborhood and then returns to pick up the next set to be delivered.
II. A postal carrier picks up mail from six collection boxes around a city.	
	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

33.	For which of the two situations below is it desirable to find an Euler circuit or an efficient eulerization of a graph?
I. After a storm, a health department worker inspects all the houses of a small village to check for damage.
II. A veteran planning a visit to all the war memorials in Washington D.C. plots a route to follow.	
	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

34.	For which of the two situations below is it desirable to find an Euler circuit or an efficient eulerization of a graph?
I. A street department employee must check the traffic signals at each intersection in a downtown area to be certain they are working.
II. An employee of a power company reads the electric meters outside each house along the streets in a residential area.	
	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

35.	For which of the two situations below is it desirable to find an Euler circuit or an efficient eulerization of a graph?
I. Plowing the streets of a small village after a snow.
II. Painting the lines down the center of the roads in a town with only two-way roads.	
	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

36.	After a major natural disaster, such as a flood, hurricane or tornado, many tasks need to be completed as efficiently as possible.  For which situation below would finding an Euler circuit or an efficient eulerization of a graph be the appropriate mathematical technique to apply?	
A)	Relief food supplies must be delivered to eight emergency shelters located at different sites in a large city.	
B)	The Department of Public Works must inspect traffic lights at intersections in the city to determine which are still working.	
C)	An insurance claims adjuster must visit 10 homes in various neighborhoods to write reports.	
D)	The Department of Public Works must inspect all streets in the city to remove dangerous debris.	

37.	After a major natural disaster, such as a flood, hurricane or tornado, many tasks need to be completed as efficiently as possible.  For which situation below would finding an Euler circuit or an efficient eulerization of a graph be the appropriate mathematical technique to apply?	
A)	The electric company must check several substations for malfunctions.	
B)	The gas company must check along all gas lines for possible leaks.	
C)	The phone company must respond to customers' needs in several parts of town.	
D)	The water company must spot check the integrity of eight water towers located throughout the city.	

38.	In order to eulerize the graph below, give the fewest number of edges that need to be added or duplicated?

	A)  1    B)  2    C)  3    D)  4	

39.	In order to eulerize the graph below, give the fewest number of edges that need to be added or duplicated?

	A)  4    B)  6    C)  10    D)  12	

40.	In order to eulerize the graph below, give the fewest number of edges that need to be added or duplicated?

	A)  1    B)  2    C)  3    D)  4	

41.	If a graph had 8 vertices of odd valence, what is the absolute minimum number of edges that would need to be added (duplicated) to eulerize the graph?	
	A)  2    B)  4    C)  6    D)  8	

42.	If a graph had 12 vertices of odd valence, what is the absolute minimum number of edges that would need to be added (duplicated) to eulerize the graph?	
	A)  2    B)  4    C)  6    D)  8	

43.	Which of the graphs shown below gives the best eulerization of the given graph.  (In the graphs below, added edges are denoted with zig-zag lines.)

44.	Which of the graphs shown below gives the best eulerization of the given graph.  (In the graphs below, added edges are denoted with zig-zag lines.)

45.	Which of the graphs shown below gives the best eulerization of the given graph.  (In the graphs below, added edges are denoted with zig-zag lines.)

46.	Which of the graphs shown below gives the best eulerization of the given graph.  (In the graphs below, added edges are denoted with zig-zag lines.)

47.	Suppose the edges of a graph represent streets that must be checked by a worker from the Department of Public Works.  In order to eulerize the graph, we must add three edges.  The real world interpretation of this is:	
A)	We must travel three blocks twice in our circuit.	
B)	The street department will build three new streets.	
C)	Three blocks will not be checked by the Department of Public Works.	
D)	It will take three workers to check all the streets in the city.	

48.	The map shown below illustrates part of a postal carrier's territory.  The dots indicate mailboxes to which mail must be delivered.  Which graph would be most useful for finding an efficient route for mail delivery?

49.	For the street network shown below, which graph would be most useful for routing a garbage truck?  Assume all streets are two way and that passing down a street once would be sufficient to collect from both sides.

50.	The map below shows the territory for a parking control officer.  The dots represent parking meters that need to be checked.  Which graph would be useful for finding an efficient route?

51.	In the graph below, find the largest number of paths from A to G that do not have any edges in common.

	A)  2    B)  3    C)  4    D)  5	

52.	What is the valence of vertex A in the graph below?

	A)  0    B)  1    C)  2    D)  3	

53.	Which of the graphs below are connected?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

54.	In order to eulerize the graph below, give the fewest number of edges that need to be added or duplicated.

	A)  2    B)  3    C)  4    D)  5	

55.	What is the smallest number of edges that would need to be removed to disconnect the graph below?

	A)  1    B)  2    C)  3    D)  4	

56.	What is the smallest number of edges that would need to be removed to disconnect the graph below?

	A)  1    B)  2    C)  3    D)  4	

57.	Which of the graphs below have Euler circuits?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

58.	Consider the path represented by the numbered sequences of edges in the graph below. Which path represents an Euler circuit?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

59.	Consider the path represented by the numbered sequences of edges in the graph below. Which statement is true?

A)	The path is not a circuit.	
B)	The path is an Euler circuit.	
C)	The path is a circuit, but not an Euler circuit.	
D)	None of the above	

60.	If a graph had 16 vertices of odd valence, what is the absolute minimum number of edges that would need to be added (duplicated) to eulerize the graph?	
	A)  2    B)  4    C)  6    D)  8	

Answer Key

1.	C	
2.	B	
3.	D	
4.	A	
5.	B	
6.	B	
7.	A	
8.	C	
9.	B	
10.	B	
11.	B	
12.	A	
13.	A	
14.	B	
15.	C	
16.	A	
17.	D	
18.	B	
19.	B	
20.	A	
21.	B	
22.	A	
23.	A	
24.	B	
25.	B	
26.	D	
27.	C	
28.	B	
29.	A	
30.	B	
31.	C	
32.	D	
33.	D	
34.	B	
35.	C	
36.	D	
37.	B	
38.	C	
39.	B	
40.	D	
41.	B	
42.	C	
43.	c	
44.	d	
45.	c	
46.	a	
47.	A	
48.	b	
49.	a	
50.	d	
51.	C	
52.	A	
53.	D	
54.	C	
55.	B	
56.	C	
57.	A	
58.	B	
59.	C	
60.	D