Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo

Chapter Review

Graph Basics

For the following exercises, use the given figure.
Five graphs are titled graph S, graph T, graph U, graph V, and graph W. Graph S has five vertices: a, b, c, d, and e. Edges connect a b, a c, bc, c d, c e, and d e. Graph T has four vertices: a, b, d, and e. Edges connect a b, a e, b d, and d e. Graph U has 6 vertices: a, b, f, c, d, and e. Edges connect ab, a f, f d, b c, c d, d e, c e, and a c. Graph V has four vertices: a, b, d, and e. Edges connect a b, a d, a e, b d, and d e. Graph W has four vertices: a, b, d, and e. Edges connect a b, a d, and d e.
1 .
Determine the number of vertices in Graph S.
2 .
Identify the graph with the fewest edges.
3 .
Name the vertices in Graph U.
4 .
Identify any pairs of vertices in Graph S that are not adjacent.
5 .
Which graphs only has vertices of degree 2?
6 .
Identify the graph in which the sum of the degrees of the vertices is 16.
7 .
Amazon.com has a network of warehouses that are used to move packages around the United States. Delivery trucks from warehouse deliver packages to other locations. These mail trucks also pick up packages to bring back to their home warehouse. Explain how a graph or multigraph might be drawn to model this scenario by identifying the objects that could be represented by vertices and the connections that could be represented by edges. Indicate whether a graph or a multigraph would be a better model.
8 .
Eduardo has two groups of four friends, group A and group B. Within each group, each of the members of the group are friends with each other but not with those in the other group. The individuals in group A have no other friends, but the individuals in group B each has their own group of four friends, and the individuals within those groups are all friends with each other, but with no one outside their own group. Draw a graph to represent the given scenario.

Graph Structures

For the following exercises, use the given figure.
Four graphs are titled graph A, graph B, graph C, and graph D. Graph A shows edges connecting the vertices: v q, v p, v u, v t, v s and v r. Graph B shows edges connecting the vertices: p q, q s, s t, t p, v u, and v r. Graph C shows edges connecting the vertices: p q, p u, u t, u v, t s, q s, and p t. Graph D shows edges connecting the vertices: v p, v q, v u, v t, v r, v s, p q, u t, and r s.
9 .
Explain why Graph B is not a subgraph of Graph C.
10 .
Identify any graphs that have a quadrilateral cyclic subgraph and name the vertices.
11 .
Identify a clique in Graph C by listing its vertices.
12 .
Draw a graph with the following characteristics: largest clique has 4 vertices, a pentagonal cyclic subgraph, exactly two vertices of degree 4.
13 .
How many edges are in a complete graph with 12 vertices?
14 .
How many triangles are in a complete graph with 11 vertices?

Comparing Graphs

15 .
Identify three differences between Graph 1 and Graph 2 that demonstrate the graphs are not isomorphic.
Two graphs. Graph 1 has four vertices: a, b, c, and d. Edges connect a b, b d, d c, c a, ad, and c b. Graph2 has five vertices: e, f, g, h, and i. Edges connect e f, f, I h, h e, h g, and g f.
For the following exercises, use the given figure.
Four graphs. Graph 3 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 1, 2, 3, and 4. The vertices of the second quadrilateral are 5, 6, 7, and 8. An edge connects 2 to 6. Graph 4 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 9, 10, 13, and 14. The vertices of the second quadrilateral are 15, 11, 17, and 16. A vertex, 12 is at the intersection of 15 and 11 and 13 and 10. Graph 5 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 18, 19, 20, and 21. The vertices of the second quadrilateral are 22, 23, 24, and 25. Graph 6 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 28, 32, 33, and 34. The vertices of the second quadrilateral are 27, 29, 30, and 31 A vertex, 26 is at the intersection of 28 and 32 and 27 and 31.
16 .
Determine if Graph 3 is isomorphic to Graph 4. If so, identify a correspondence between the vertices which demonstrates the isomorphism. If not, identify at least two characteristics that verifies this.
17 .
Determine if Graph 3 is isomorphic to Graph 5. If so, identify a correspondence between the vertices that demonstrates the isomorphism. If not, identify a characteristic that verifies this.
18 .
Consider Graph 4 and Graph 5. Determine if one graph is a subgraph of the other. If so, give a correspondence between vertices that demonstrates this relationship. If not, identify conflicting characteristics.
For the following exercises, use the given figure.
Four graphs. Graph 7 has five vertices: a to e. All the vertices are interconnected except a b. Graph 8 has five vertices: f to j. All the vertices are interconnected except f g and g i. Graph 9 has five vertices: k to o. All the vertices are interconnected except l m and k o. Graph 10 has five vertices; p to t. All the vertices are interconnected except p r and t s.
19 .
Draw the complements of Graphs 7 and 9. Determine whether the graphs you drew are isomorphic to each other and explain how you know. Use this information to determine whether Graphs 7 and 8 are isomorphic.
20 .
Draw the complements of Graphs 7 and 10. Determine whether the graphs you drew are isomorphic to each other and explain how you know. Use this information to determine whether Graphs 7 and 10 are isomorphic.
21 .
Draw the complements of Graphs 8 and 9. Determine whether the graphs you drew are isomorphic to each other and explain how you know. Use this information to determine whether Graphs 8 and 9 are isomorphic.

Navigating Graphs

For the following exercises, use Graph A in the given figure. Consider each sequence of vertices. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.
Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.
22 .
edbef
23 .
ebdefcbd
24 .
efbd
For the following exercises, use Graph K in Figure 12.352. Identify each sequence of vertices as a closed walk, circuit (closed trail), and/or directed cycle (closed path). Indicate all that apply.
25 .
noqnpmn
26 .
mnoqnponm
27 .
poqnmp
For the following exercises, use Graphs A and K in Figure 12.352.
28 .
Are Graphs A and K planar graphs? What does your answer tell you about the chromatic number of each graph?
29 .
How many vertices are in the largest complete subgraph of Graph A? What does this tell you about the chromatic number of Graph A?
30 .
Create a coloring of Graph A, which uses exactly four colors, or explain why it is not possible.
31 .
Create a coloring of Graph K, which uses exactly two colors, or explain why it is not possible.
32 .
Determine the chromatic number of Graph A. Give a coloring that supports your conclusion.
33 .
Determine the chromatic number of Graph K. Give a coloring that supports your conclusion.

Euler Circuits

For the following exercises, use the graphs and multigraphs shown. Identify any graphs and/or multigraphs with the given characteristics. If there are none, state so.
Five graphs. Graph 11 has 8 vertices. Edges connect r s, s v, v u u r, t x, t w, and x w. Graph 12 has 7 vertices. Edges connect e f, f g, g e, g d, e d, e a, d a, d c, g c, c a, c b, and a b. Graph 13 has 5 vertices. Edges connect n o, n q, o m, o p, m p, m q, and q p. Multigraph 14 has 5 vertices. The edges are labeled from A to H. Multigraph 15 has 5 vertices. The edges are labeled from K to U.
34 .
connected
35 .
disconnected
36 .
Eulerian

Euler Trails

For the following exercises, use the graphs and multigraphs in Figure 12.354.
37 .
List the set of vertices for each component in Graph 13.
38 .
Determine whether the sequence of edges represents an Euler circuit in Multigraph 15:
KLNMOSTQUPR
39 .
Find an Euler circuit beginning and ending at vertex g in Graph 12 if one exists. Otherwise, explain how you know such an Euler circuit does not exist.
40 .
Give an example of a pair of edges that could be duplicated to eulerize Multigraph 14.
For the following exercises, use the graphs and multigraphs in Figure 12.354. Identify any graphs and/or multigraphs with the given characteristics. If there are none, state so.
41 .
Exactly two vertices of odd degree
42 .
Has an Euler trail
43 .
Has exactly one local bridge
For the following exercises, use the graphs and multigraphs in Figure 12.354. In each exercise a graph and a sequence of vertices are given.
44 .
Determine whether the sequence of edges, ABCHGDFE, is an Euler trail, an Euler circuit, or neither for the graph. If it is neither, explain why.
45 .
Suppose that an edge were added to Graph 11 between vertices s and w. Determine if the graph would have an Euler trail or an Euler circuit, and find one.

Hamilton Cycles

For the following exercises, refer to the graph in the given figure.
A graph has 7 vertices. The vertices are labeled a, b, c, d, e, f, and g. Edges connect a b, a d, d f, d e, f c, f g, c g, and e b.
46 .
A student has been asked to use Fleury’s algorithm to construct an Euler trail in the given graph. The student decides to begin the trail at vertex d. Is this a good choice, why or why not?
47 .
A student who is using Fleury’s algorithm to construct an Euler trail has decided to begin with fdab → …. If the student is off to a good start, help the student by completing the Euler trail. If the student has made an error, explain the error.
48 .
Use Fleury’s algorithm to construct an Euler trail for Graph 16 beginning at the vertex of your choice.
For the following exercises, use the graphs from the given figures to determine whether the sequence of vertices in the given graph is a Hamilton cycle, an Euler circuit, both, or neither.
Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.
Graph F has five vertices. The vertices are a, b, c, d, and e. Edges connect a c, a b, e c, e b, c b, c d, and b d.
49 .
Graph F. abecbdca
50 .
Graph K. mnqopm
51 .
Graph A. bdefcbe
For the following exercises, evaluate the factorial expression for the given value of n .
52 .
( n 1 ) ! , n = 12
53 .
( n 1 ) ! , n = 14
54 .
Calculate the number of distinct Hamilton cycles in a complete graph with 13 vertices.
For the following exercises, use the figure shown to find the weight of each Hamilton cycle.
Graph Z has nine vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows. 1, q to t. 2, s to v. 3, r to s. 4, q to u. 5, u to y. 6, r to v. 7, r to u. 8, v to y. 9, w to x. 10, x to y. 1, u to x. 12, t to w. 13, q to r. 14, t to u. 15, u to v.
55 .
qtwxuyvsrq
56 .
wxyuvsrqtw

Hamilton Paths

For the following exercises, use the figure shown to determine whether the sequence of vertices in the given graph is a Hamilton path, an Euler trail, both, or neither.
Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.
57 .
Graph A. ebcfebe
58 .
Graph A. bcfedbe
59 .
Graph K. nqopm
60 .
Graph K. oqmnp
Recall the three common scenarios in which it is not possible to have a Hamilton between two vertices.
Scenario 1: If an edge ab is a bridge, then there is no Hamilton path between a pair of vertices that are on the same side of edge ab.
Scenario 2: If an edge ab is a bridge with at least three components on each side, then there is no Hamilton path beginning or ending at a or b.
Scenario 3: If a graph is composrd of two cycles joined only at a single vertex p, and v is any vertex that is not adjacent to p, then there are no Hamilton paths beginning or ending at p.
For the following exercises, identify the scenario that guarantees there is no Hamilton path between the given pair of vertices in the given graph.
A graph has 7 vertices. The vertices are labeled a, b, c, d, e, f, and g. Edges connect a b, a d, d f, d e, f c, f g, c g, and e b.
61 .
Vertices a and e.
62 .
Vertices d and f.
The principal of an elementary school plans to visit each classroom exactly once before leaving for the day. The floor plan of the school is given. Use this information for the following exercises.
A floor plan of an elementary school. It has three blocks. The first block has front office A. The second block has three rooms: G, H, and I. The third block has five rooms: B, C, D, E, and F. Exit is at the top-right.
63 .
Draw a graph to represent the floor plan for the elementary school in which each vertex is a room and an edge between two vertices indicates that there is a path between the two rooms that does not pass the door to another room.
64 .
Use your graph to find a route that the principal can take beginning at the Front Office in room A, visiting each room exactly once (without passing by another room), and ending at room F, which is next to the exit.
65 .
Would the route you found be best to trace out a Hamilton path, an Euler trail, both, or neither in the graph you drew? Explain how you know.

Traveling Salesperson Problem

For the following exercises, determine whether the algorithm described is a greedy algorithm or a brute force algorithm.
66 .
A lumber distributor is loading pallets onto trucks with the intention of using the fewest trucks possible to send a shipment. The distributor loads the pallets with the greatest length that will fit on the truck first and continues loading until no more pallets will fit. Then the next truck is loaded using the same approach.
67 .
A traveler wants to visit five cities by airplane. The traveler lists all the possible orders in which the cities can be visited then calculates the best airfare for each itinerary and selects the least expensive option.
For the following exercises, list all the distinct Hamilton cycles beginning at the given vertex in the given graph. Indicate which pairs of Hamilton cycles are reverses of each other.
Two graphs are labeled graph 17 and graph 18. Graph 17 has four vertices, a, b, c, and d. The edges are labeled as follows: a to b, 13.3; b to c, 2.0; c to d, 8.7; d to a, 9.3; a to c, 1.5; b to d, 5.2. Graph 18 has five vertices, m, q, n, p, and o. The edges are labeled as follows: m to n, 250; m to q, 100; m to p, 110; m to 0, 300; q o n, 90; q to o, 210; n to p, 75; q to p, 50; p to o, 425; n to o, 225.
68 .
Graph 17, vertex a
69 .
Graph 18, vertex m
For the following exercises, find a Hamilton cycle of least weight for the given graph in Figure 12.362, beginning at the given vertex, and using the brute force method. What is the weight of the cycle?
70 .
Graph 18; vertex m
71 .
Graph 17; vertex a
For the following exercises, find a Hamilton cycle of low weight for the given graph in Figure 12.362, beginning at the given vertex, and using the nearest neighbor method. What is the weight of the cycle?
72 .
Graph 18 vertex m
73 .
Graph 17, vertex a
74 .
The products at a particular factory are manufactured in phases. The same equipment is utilized for each phase, but it must be formatted differently to accomplish different tasks. The transition time to convert between a format for one task and another task varies. The times are given in the table below.

Task A B C D E F G
A 0 75 130 45 120 70 100
B 75 0 140 65 115 25 60
C 130 140 0 35 55 20 125
D 45 65 35 0 50 30 40
E 120 115 55 50 0 95 145
F 70 25 20 30 95 0 15
G 100 60 125 40 145 15 0
Use the table to draw a graph in which the vertices represent tasks A, C, D, F, and G, and the weights of the edges indicate the times in minutes to transition between pairs of tasks. Use the nearest neighbor method to find an order in which to complete tasks A, C, D, F, and G, which keeps the transition times down and ends with the same set up as it began so that the factory is ready start the next batch. Assume that there are no restrictions on which tasks can be completed in which order. Hint: The nearest neighbor algorithm may give a different result depending on which vertex is the starting vertex; so, you must check all possibilities.

Trees

For the following exercises, draw a graph with the given characteristics.
75 .
A tree with eight vertices, exactly two of degree three.
76 .
A connected graph with eight vertices, exactly two of degree 3, which is not a tree.
For the following exercises, identify each type of graph in the given figure: tree graph, star graph, starlike graph, line graph, lobster graph, caterpillar graph, and/or forest graph.
Two graphs are labeled graph 19 and graph 20. Graph 19 has 4 vertices. The vertices are a, b, c, and d. Edges connect ab, ac, and ad. Graph 20 has 8 vertices. The vertices are labeled a to h. Edges connect b a, b d, b c, f e, f h, and f g.
77 .
Graph 19
78 .
Graph 20
For the following exercises, use the figure shown to draw three possible spanning trees that fit the given description.
Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and ef. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.
79 .
Three spanning trees of Graph A, which include both edges be and de.
80 .
Three spanning trees of Graph K, which include edges mn and oq, but do not include no.
For the following exercises, use Kruskal’s Algorithm to find a minimum spanning tree of the given graph. Graph it and calculate its weight.
Two graphs are labeled graph 17 and graph 18. Graph 17 has four vertices, a, b, c, and d. The edges are labeled as follows: a to b, 13.3; b to c, 2.0; c to d, 8.7; d to a, 9.3; a to c, 1.5; b to d, 5.2. Graph 18 has five vertices, m, q, n, p, and o. The edges are labeled as follows: m to n, 250; m to q, 100; m to p, 110; m to 0, 300; q o n, 90; q to o, 210; n to p, 75; q to p, 50; p to o, 425; n to o, 225.
81 .
Graph 17
82 .
Graph 18
Citation/Attribution

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Citation information

© Jul 25, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.