Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo

Menu
Table of contents
  1. Preface
  2. 1 Sets
    1. Introduction
    2. 1.1 Basic Set Concepts
    3. 1.2 Subsets
    4. 1.3 Understanding Venn Diagrams
    5. 1.4 Set Operations with Two Sets
    6. 1.5 Set Operations with Three Sets
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  3. 2 Logic
    1. Introduction
    2. 2.1 Statements and Quantifiers
    3. 2.2 Compound Statements
    4. 2.3 Constructing Truth Tables
    5. 2.4 Truth Tables for the Conditional and Biconditional
    6. 2.5 Equivalent Statements
    7. 2.6 De Morgan’s Laws
    8. 2.7 Logical Arguments
    9. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  4. 3 Real Number Systems and Number Theory
    1. Introduction
    2. 3.1 Prime and Composite Numbers
    3. 3.2 The Integers
    4. 3.3 Order of Operations
    5. 3.4 Rational Numbers
    6. 3.5 Irrational Numbers
    7. 3.6 Real Numbers
    8. 3.7 Clock Arithmetic
    9. 3.8 Exponents
    10. 3.9 Scientific Notation
    11. 3.10 Arithmetic Sequences
    12. 3.11 Geometric Sequences
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  5. 4 Number Representation and Calculation
    1. Introduction
    2. 4.1 Hindu-Arabic Positional System
    3. 4.2 Early Numeration Systems
    4. 4.3 Converting with Base Systems
    5. 4.4 Addition and Subtraction in Base Systems
    6. 4.5 Multiplication and Division in Base Systems
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  6. 5 Algebra
    1. Introduction
    2. 5.1 Algebraic Expressions
    3. 5.2 Linear Equations in One Variable with Applications
    4. 5.3 Linear Inequalities in One Variable with Applications
    5. 5.4 Ratios and Proportions
    6. 5.5 Graphing Linear Equations and Inequalities
    7. 5.6 Quadratic Equations with Two Variables with Applications
    8. 5.7 Functions
    9. 5.8 Graphing Functions
    10. 5.9 Systems of Linear Equations in Two Variables
    11. 5.10 Systems of Linear Inequalities in Two Variables
    12. 5.11 Linear Programming
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  7. 6 Money Management
    1. Introduction
    2. 6.1 Understanding Percent
    3. 6.2 Discounts, Markups, and Sales Tax
    4. 6.3 Simple Interest
    5. 6.4 Compound Interest
    6. 6.5 Making a Personal Budget
    7. 6.6 Methods of Savings
    8. 6.7 Investments
    9. 6.8 The Basics of Loans
    10. 6.9 Understanding Student Loans
    11. 6.10 Credit Cards
    12. 6.11 Buying or Leasing a Car
    13. 6.12 Renting and Homeownership
    14. 6.13 Income Tax
    15. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  8. 7 Probability
    1. Introduction
    2. 7.1 The Multiplication Rule for Counting
    3. 7.2 Permutations
    4. 7.3 Combinations
    5. 7.4 Tree Diagrams, Tables, and Outcomes
    6. 7.5 Basic Concepts of Probability
    7. 7.6 Probability with Permutations and Combinations
    8. 7.7 What Are the Odds?
    9. 7.8 The Addition Rule for Probability
    10. 7.9 Conditional Probability and the Multiplication Rule
    11. 7.10 The Binomial Distribution
    12. 7.11 Expected Value
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  9. 8 Statistics
    1. Introduction
    2. 8.1 Gathering and Organizing Data
    3. 8.2 Visualizing Data
    4. 8.3 Mean, Median and Mode
    5. 8.4 Range and Standard Deviation
    6. 8.5 Percentiles
    7. 8.6 The Normal Distribution
    8. 8.7 Applications of the Normal Distribution
    9. 8.8 Scatter Plots, Correlation, and Regression Lines
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  10. 9 Metric Measurement
    1. Introduction
    2. 9.1 The Metric System
    3. 9.2 Measuring Area
    4. 9.3 Measuring Volume
    5. 9.4 Measuring Weight
    6. 9.5 Measuring Temperature
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  11. 10 Geometry
    1. Introduction
    2. 10.1 Points, Lines, and Planes
    3. 10.2 Angles
    4. 10.3 Triangles
    5. 10.4 Polygons, Perimeter, and Circumference
    6. 10.5 Tessellations
    7. 10.6 Area
    8. 10.7 Volume and Surface Area
    9. 10.8 Right Triangle Trigonometry
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  12. 11 Voting and Apportionment
    1. Introduction
    2. 11.1 Voting Methods
    3. 11.2 Fairness in Voting Methods
    4. 11.3 Standard Divisors, Standard Quotas, and the Apportionment Problem
    5. 11.4 Apportionment Methods
    6. 11.5 Fairness in Apportionment Methods
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  13. 12 Graph Theory
    1. Introduction
    2. 12.1 Graph Basics
    3. 12.2 Graph Structures
    4. 12.3 Comparing Graphs
    5. 12.4 Navigating Graphs
    6. 12.5 Euler Circuits
    7. 12.6 Euler Trails
    8. 12.7 Hamilton Cycles
    9. 12.8 Hamilton Paths
    10. 12.9 Traveling Salesperson Problem
    11. 12.10 Trees
    12. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  14. 13 Math and...
    1. Introduction
    2. 13.1 Math and Art
    3. 13.2 Math and the Environment
    4. 13.3 Math and Medicine
    5. 13.4 Math and Music
    6. 13.5 Math and Sports
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  15. A | Co-Req Appendix: Integer Powers of 10
  16. Answer Key
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
  17. Index

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.
e → d → b → e → f
23.
e → b → d → e → f → c → b → d
24.
e → f → b → d
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.
n → o → q → n → p → m → n
26.
m → n → o → q → n → p → o → n → m
27.
p → o → q → n → m → p
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:
K → L → N → M → O → S → T → Q → U → P → R
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, A → B → C → H → G → D → F → E, 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 f → d → a → b → …. 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. a → b → e → c → b → d → c → a
50.
Graph K. m → n → q → o → p → m
51.
Graph A. b → d → e → f → c → b → e
For the following exercises, evaluate the factorial expression for the given value of n.
52.
\left( {n - 1} \right)!, n = 12
53.
\left( {n - 1} \right)!, 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.
q → t → w → x → u → y → v → s → r → q
56.
w → x → y → u → v → s → r → q → t → w
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. e → b → c → f → e → b → e
58.
Graph A. b → c → f → e → d → b → e
59.
Graph K. n → q → o → p → m
60.
Graph K. o → q → m → n → p
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

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

© Apr 17, 2023 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.