MA 111001 & 002
Practice for Exam 2
Use the following three graphs for questions 110:
1. Which of these graphs have an Euler Circuit?
a. Graph 1 b. Graph 2 c. Graph 3 d. Graphs 1&2 e. Graphs 2&3 f. Graphs 1&3 g. all h. none
2. One Euler Circuit appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________. If there is no Euler Circuit in any of the graphs,
write None.
3. Which of these graphs have an Euler Path?
a. Graph 1 b. Graph 2 c. Graph 3 d. Graphs 1&2 e. Graphs 2&3 f. Graphs 1&3 g. all h. none
4. One Euler Path appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________. If there is no Euler Path in any of the graphs,
write None.
5. Which of these graphs have a Hamilton Circuit?
a. Graph 1 b. Graph 2 c. Graph 3 d. Graphs 1&2 e. Graphs 2&3 f. Graphs 1&3 g. all h. none
6. One Hamilton Circuit appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________. If there is no Hamilton Circuit in any of the
graphs, write None.
7. Which of these graphs have a Hamilton Path?
a. Graph 1 b. Graph 2 c. Graph 3 d. Graphs 1&2 e. Graphs 2&3 f. Graphs 1&3 g. all h. none
8. One Hamilton Path appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________. If there is no Hamiliton Path in any of the
graphs, write None.
9. Find a circuit on Graph 3 that begins at vertex A and contains vertex C, but not vertex E. Is this an
Euler Circuit?
10. The vertex set of Graph 2 is __________________________________.
The edge set of Graph 2 is _________________________________________.
11. Find an optimal Eulerization for the graph below. If this were the graph representation of a
neighborhood, in which a security guard needs to walk each block at least once, beginning and
ending at the labeled vertex, how many total blocks must he walk?
12. Define a Complete Graph. Draw the graph K5. How many Hamilton Circuits are there in K5?
13. Fill in the chart:
Vertex/Edge Set:  Number of and Degree of Vertices  Drawing of Graph(Place an * by drawing if there is more than one graph with the given description)  Contains:A)Euler Circuit
B)Euler Path C)Both D)Neither E)Not Enough Info 
V={dog, cat, fish, plant, man, bear, pig, car}E={Edges connect vertices if one might eat the other.} 

Ten verticesFour having degree 2
Two having degree 1 Four having degree 3 

V={A,B,C,D,E,F,G}E={AB, AC, AD, AG, BA, BB, CD, DG, EE, FG} 

Six vertices, each having degree 2.  
14. Find an optimal coloring for the graph below. How many colors do you need?
15. There may be a bonus question involving a Sudoku puzzle. Here are some practice puzzles:
Beginner
Easy
Medium
Diabolical (This is just for fun, for those of you who weren’t challenged enough in class).
MA 111001 & 002
Practice for Exam 2
Use the following three graphs for questions 110:
1. Which of these graphs have an Euler Circuit?
c. Graph 3
2. One Euler Circuit appearing in Graph 3 is (begin with vertex A and list all vertices visited in
proper order) ABCEFGAFCDA. If there is no Euler Circuit in any of the graphs,
write None.
3. Which of these graphs have an Euler Path?
a. Graph 1
4. One Euler Path appearing in Graph 1 is (list all vertices visited in proper order) DAEBCABDC. If there is no Euler Path in any of the graphs, write None.
5. Which of these graphs have a Hamilton Circuit?
d. Graphs 1&2
6. One Hamilton Circuit appearing in Graph 1 is (begin with vertex A and list all vertices visited in
proper order) AEBCDA. If there is no Hamilton Circuit in any of the graphs, write None.
7. Which of these graphs have a Hamilton Path?
g. all
8. One Hamilton Path appearing in Graph 1 is (begin with vertex A and list all vertices visited in
proper order) AEBCD. If there is no Hamiliton Path in any of the graphs, write None.
9. Find a circuit on Graph 3 that begins at vertex A and contains vertex C, but not vertex E. Is this an
Euler Circuit? ABCDA – No, it is not Euler because it doesn’t contain all of the edges in the graph.
10. The vertex set of Graph 2 is {A,B,C,D,E,F,G}.
The edge set of Graph 2 is {AB, AD, AF, AG, BC, BE, BD, BG, CD, CE, CF, EF, FG}.
11. Find an optimal Eulerization for the graph below. If this were the graph representation of a
neighborhood, in which a security guard needs to walk each block at least once, beginning and
ending at the labeled vertex, how many total blocks must he walk? Add double edges until all odd vertices are even. I did it with 40 total edges. Can you find a way with less?
12. Define a Complete Graph. Draw the graph K5. How many Hamilton Circuits are there in K22? A complete graph is one in which each vertex shares an edge with every other vertex. K5 is the complete graph with 5 vertices. It is usually drawn as a pentagon with a star inside. There are (221)!=21*20*19*…*3*2*1 Hamilton Circuits in K22.
13. Fill in the chart:
Vertex/Edge Set:  Number of and Degree of Vertices  Drawing of Graph(Place an * by drawing if there is more than one graph with the given description)  Contains:A)Euler Circuit
B)Euler Path C)Both D)Neither E)Not Enough Info 
V={dog, cat, fish, plant, man, bear, pig, car}E={Edges connect vertices if one might eat the other.} 
Varies  Varies  E 
Varies  Ten verticesFour having degree 2
Two having degree 1 Four having degree 3 
D  
V={A,B,C,D,E,F,G}E={AB, AC, AD, AG, BA, BB, CD, DG, EE, FG} 
7 vertices
1 with degree 5 1 with degree 4 2 with degree 3 2 with degree 2 1 with degree 1 
D  
Varies  Six vertices, each having degree 2.  E  
Vertex Set {A, B, C, D, E, F, G}
Edge Set {AD, BC, BG, BD, CD, CE, DE, DF, DG, EG, FG} 
7 vertices
Count degrees.

D 
14. Find an optimal coloring for the graph below. How many colors do you need? 3 colors
1 Response to “Exam 2 Review”