Finite Mathematics Quiz: Minimum Spanning Trees

8 questions · exam conditions

0:00

Minimum Spanning TreesQuestion 1 of 8

In a weighted graph, Prim's algorithm is used starting from vertex S. After 3 iterations, vertices S, A, and B have been added to the minimum spanning tree with edges SA (weight 4) and AB (weight 7). The remaining vertices C, D, E have the following minimum distances to the current tree: C is 5 units from A, D is 3 units from B, and E is 8 units from S. Which vertex will be added in the 4th iteration?

Vertex C, because it has the smallest vertex label alphabetically among remaining vertices

Vertex D, because it has the minimum distance to any vertex in the current spanning tree

Vertex E, because it connects directly to the starting vertex S

Vertex C, because it connects to vertex A which was added most recently to the tree

← Back to quizzes

Finite Mathematics Quiz

Finite Mathematics Quiz: Minimum Spanning Trees

Practice Minimum Spanning Trees in Finite Mathematics with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Minimum Spanning Trees, giving you a quick way to practice the rules, question types, and explanations that matter most for Finite Mathematics.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

Vertex C, because it has the smallest vertex label alphabetically among remaining vertices
Vertex D, because it has the minimum distance to any vertex in the current spanning tree (correct answer)
Vertex E, because it connects directly to the starting vertex S
Vertex C, because it connects to vertex A which was added most recently to the tree

Explanation: Prim's algorithm always selects the vertex with minimum distance to any vertex already in the spanning tree. Among C (distance 5), D (distance 3), and E (distance 8), vertex D has the smallest distance (3). Choice A incorrectly uses alphabetical order. Choice C incorrectly prioritizes connection to the starting vertex. Choice D incorrectly prioritizes the most recently added vertex.

Question 2

Two different minimum spanning tree algorithms are applied to the same weighted graph. Algorithm X produces a spanning tree with total weight 50, while Algorithm Y produces a spanning tree with total weight 48. What can be concluded?

Algorithm Y is more efficient and found a better solution than Algorithm X
The graph has multiple minimum spanning trees with different total weights
At least one of the algorithms was implemented incorrectly or applied to different graphs (correct answer)
Algorithm X used Prim's method while Algorithm Y used Kruskal's method, explaining the difference

Explanation: Any correct minimum spanning tree algorithm applied to the same graph must produce spanning trees with identical total weights (though the trees themselves may differ if there are ties in edge weights). Since the weights differ (50 vs 48), at least one algorithm was implemented incorrectly, or they were applied to different graphs. Choice A misunderstands that MST weight is unique. Choice B is impossible. Choice D incorrectly suggests different algorithms can yield different minimum weights.

Question 3

A minimum spanning tree of a connected graph with 6 vertices has total weight 45. If one edge of weight 8 is removed from this spanning tree, creating two separate components, what is the minimum possible weight of the lightest edge that could reconnect these components?

At least 8, since any reconnecting edge must be heavier than the removed edge
Exactly 8, since the removed edge was the unique lightest reconnecting option
At least 9, since any lighter edge would have been chosen instead in the original MST (correct answer)
Cannot be determined without knowing the weights of all edges in the original graph

Explanation: In a minimum spanning tree, every edge not in the MST creates a cycle when added. Since the edge of weight 8 was in the MST, any other edge connecting the two components created by removing it must have weight > 8, otherwise that edge would have been chosen instead during MST construction. The minimum possible weight is therefore at least 9. Choice A allows weight 8. Choice B assumes uniqueness. Choice D is incorrect since MST properties determine the answer.

Question 4

Let $G$ be a connected, weighted graph with $n$ vertices and distinctly weighted edges. Let $T_{min}$ be the unique minimum spanning tree and $T_{max}$ be the unique maximum spanning tree of $G$ . Which of the following statements must be true?

The edge with the largest weight in $G$ can never be in $T_{min}$ .
$T_{min}$ and $T_{max}$ can have no edges in common.
The number of edges in $T_{min}$ is the same as the number of edges in $T_{max}$ . (correct answer)
The shortest path between any two vertices in $G$ is always composed of edges from $T_{min}$ .

Explanation: By definition, any spanning tree (minimum, maximum, or otherwise) of a graph with

n

vertices must contain exactly

n-1

edges. Therefore,

T_{min}

and

T_{max}

must have the same number of edges. Distractor A is false if the largest-weight edge is a bridge. Distractor B is false if a bridge is part of both. Distractor D is false because an MST minimizes total weight, not path length between specific vertices; the shortest path may use edges not in the MST.

Question 5

A fiber-optic network connecting 5 data centers (A, B, C, D, E) is configured as a minimum spanning tree with a total cable length of 40 km. A new data center, F, is to be added to the network. The costs to lay new cable from F to the existing centers are: A=12 km, B=10 km, C=15 km, D=9 km, E=14 km. What will be the total cable length of the new minimum spanning tree that connects all six data centers?

49 km (correct answer)
52 km
60 km
100 km

Explanation: The original network of 5 data centers forms a connected component with a total weight of 40 km. To connect the new data center F to this existing network with minimum additional cost, we must add the single cheapest edge from F to any of the existing centers. This is an application of Prim's algorithm logic. The possible new edges have lengths 12, 10, 15, 9, and 14 km. The minimum of these is 9 km (to center D). The total length of the new MST will be the length of the old MST plus the length of this cheapest new connection:

40 \text{ km} + 9 \text{ km} = 49 \text{ km}

Question 6

A connected graph has 7 vertices and 12 edges. After running a minimum spanning tree algorithm, exactly how many edges are in the resulting spanning tree, and how many edges from the original graph are NOT included?

6 edges in the spanning tree, 6 edges not included (correct answer)
6 edges in the spanning tree, 5 edges not included
7 edges in the spanning tree, 5 edges not included
7 edges in the spanning tree, 6 edges not included

Explanation: Any spanning tree of a connected graph with

n

vertices contains exactly

n-1

edges. With 7 vertices, the spanning tree has

7-1=6

edges. Since the original graph has 12 edges, the number not included is

12-6=6

. Choice B miscalculates excluded edges. Choices C and D incorrectly state 7 edges in the spanning tree, which would create a cycle.

Question 7

Let $G$ be a connected, weighted graph with 10 vertices. A minimum spanning tree (MST) for $G$ is found with a total weight of 120. It is then discovered that an edge $e_1$ not in this MST has the same weight as an edge $e_2$ that is in the MST. Adding $e_1$ to the MST and removing $e_2$ results in a new spanning tree. What can be definitively concluded about the minimum spanning trees of graph $G$ ?

The initially found spanning tree is not a minimum spanning tree.
The graph $G$ must have at least two distinct minimum spanning trees. (correct answer)
The graph $G$ cannot have a unique minimum spanning tree.
The total weight of any spanning tree that includes edge $e_1$ must be greater than 120.

Explanation: If adding an edge

e_1

(not in an MST) and removing an edge

e_2

(in the MST) creates a new spanning tree, and if

weight(e_1) = weight(e_2)

, then the new spanning tree has the same total weight as the original MST (

120 - weight(e_2) + weight(e_1) = 120

). Since the new spanning tree has the same minimum weight, it is also an MST. Because the set of edges is different, the graph has at least two distinct MSTs.

Question 8

In applying Kruskal's algorithm to a weighted graph, an edge of weight $w$ is rejected (not added to the spanning tree). What can be concluded about this edge?

The edge has weight greater than the maximum weight in the final minimum spanning tree
The edge weight $w$ is larger than all previously considered edges in the algorithm
This edge connects two vertices that are already in different components of the partial tree
Adding this edge to the current partial spanning tree would create a cycle with existing edges (correct answer)

Explanation: When you encounter questions about Kruskal's algorithm, focus on understanding why edges get rejected during the minimum spanning tree construction process. Kruskal's algorithm works by sorting all edges by weight and considering them in order from smallest to largest. For each edge, the algorithm asks: "Would adding this edge create a cycle?" If yes, the edge is rejected; if no, it's added to the spanning tree. The key insight is that an edge creates a cycle if and only if its endpoints are already connected through the existing partial spanning tree. Answer D correctly captures this fundamental principle. When Kruskal's algorithm rejects an edge, it's because adding that edge would connect two vertices that are already connected via some other path in the current partial tree, thus forming a cycle. This is the only reason Kruskal's rejects edges. Answer A is wrong because rejected edges can have weights smaller than, equal to, or larger than the maximum weight in the final tree. Weight alone doesn't determine rejection. Answer B incorrectly suggests rejection is based on comparison with previously considered edges, but Kruskal's considers edges in weight order, so this scenario is impossible. Answer C contains a logical error—it says the vertices are in "different components," but rejection actually occurs when vertices are in the same component (already connected). Remember this key pattern: In Kruskal's algorithm, edge rejection always means "this would create a cycle." The algorithm's only concern is connectivity, not weight comparisons with other edges.