Discrete Math Quiz: Spanning Trees And Mst

16 questions · exam conditions

0:00

Spanning Trees And MstQuestion 1 of 16

A graph has vertices $\{A, B, C, D, E\}$ with edge weights as follows: $AB = 4$ , $AC = 2$ , $AD = 7$ , $BC = 3$ , $BD = 6$ , $CD = 1$ , $CE = 5$ , $DE = 8$ . When finding the MST using Kruskal's algorithm, which edge is selected third?

Edge

BC

with weight

3

is selected as the third edge in the algorithm

Edge

AB

with weight

4

is selected as the third edge in the algorithm

Edge

AC

with weight

2

is selected as the third edge in the algorithm

Edge

CE

with weight

5

is selected as the third edge in the algorithm

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Spanning Trees And Mst

Practice Spanning Trees And Mst in Discrete Math 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 Spanning Trees And Mst, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

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

Edge $BC$ with weight $3$ is selected as the third edge in the algorithm (correct answer)
Edge $AB$ with weight $4$ is selected as the third edge in the algorithm
Edge $AC$ with weight $2$ is selected as the third edge in the algorithm
Edge $CE$ with weight $5$ is selected as the third edge in the algorithm

Explanation: Kruskal's algorithm sorts edges by weight: CD(1), AC(2), BC(3), AB(4), CE(5), BD(6), AD(7), DE(8). First iteration: select CD(1). Second iteration: select AC(2). Third iteration: BC(3) doesn't create a cycle with {CD, AC} since it connects B to the existing component {A,C,D}. Choice B is wrong because AB would be fourth. Choice C is wrong because AC is selected second, not third. Choice D is wrong because CE comes later in the sorted order.

Question 2

In Prim's algorithm, at each step we select the minimum weight edge that connects the current tree to a vertex not yet in the tree. If there are multiple edges with the same minimum weight, the choice among them affects which property of the final result?

The choice affects both the structure and total weight of the resulting spanning tree
The choice affects the structure but not the total weight of the resulting spanning tree (correct answer)
The choice affects the total weight but not the structure of the resulting spanning tree
The choice affects neither the structure nor the total weight of the resulting spanning tree

Explanation: When there are ties in edge weights during Prim's algorithm, different choices lead to different spanning tree structures, but the total weight remains the same because we're always selecting from edges with identical minimum weights at each step. This is a fundamental property of MST algorithms when ties exist. Choice A wrongly suggests weight changes. Choice C reverses the correct relationship. Choice D wrongly suggests no effect on structure.

Question 3

A spanning tree $T$ of graph $G$ has the property that adding any edge from $G$ that is not in $T$ creates exactly one cycle. If $G$ has $15$ vertices and $22$ edges, how many edges are not in $T$ ?

There are $7$ edges in $G$ that are not included in spanning tree $T$
There are $6$ edges in $G$ that are not included in spanning tree $T$
There are $8$ edges in $G$ that are not included in spanning tree $T$ (correct answer)
There are $9$ edges in $G$ that are not included in spanning tree $T$

Explanation: When you encounter spanning tree problems, focus on the fundamental property: a spanning tree of a graph with

n

vertices always contains exactly

n-1

edges, regardless of how many edges the original graph has. Since graph

G

has 15 vertices, any spanning tree

T

must contain exactly

15-1 = 14

edges. This is because a spanning tree connects all vertices with the minimum number of edges needed to avoid cycles. Given that

G

has 22 total edges, the number of edges not in

T

22 - 14 = 8

edges. The property mentioned in the problem—that adding any excluded edge creates exactly one cycle—confirms this is indeed a valid spanning tree, but doesn't change the edge count calculation. Looking at the wrong answers: Answer A suggests 7 missing edges, which would mean the spanning tree has 15 edges (creating a cycle). Answer B suggests 6 missing edges, implying 16 edges in the tree (multiple cycles). Answer D suggests 9 missing edges, meaning only 13 edges in the tree (leaving vertices disconnected, so not spanning). Answer C correctly identifies 8 edges not in

T

. Study tip: Memorize the spanning tree formula: for any connected graph with

n

vertices, every spanning tree has exactly

n-1

edges. This makes spanning tree problems straightforward—just subtract

(n-1)

from the total edge count to find excluded edges.

Question 4

A connected graph $G$ has $n$ vertices and $m$ edges where $m > n$ . After running Kruskal's algorithm, suppose exactly $k$ edges were rejected because they would have created cycles. What is the relationship between $k$ , $m$ , and $n$ ?

The number of rejected edges satisfies $k = n - m + 1$ , representing the deficit in edges for complete connectivity
The number of rejected edges satisfies $k = m - n$ , representing the difference between available and needed edges
The number of rejected edges satisfies $k = m - n - 1$ , representing edges beyond the minimum connectivity requirement
The number of rejected edges satisfies $k = m - n + 1$ , representing excess edges beyond tree requirement (correct answer)

Explanation: When you encounter questions about minimum spanning trees and Kruskal's algorithm, focus on the fundamental relationship between edges in trees versus general graphs. A tree with

n

vertices always has exactly

n-1

edges—this is a core property that connects to cycle detection. Kruskal's algorithm builds a minimum spanning tree by adding edges in order of increasing weight, rejecting any edge that would create a cycle. Since the final spanning tree must have exactly

n-1

edges and the original graph has

m

edges, the algorithm accepts

n-1

edges and rejects

m-(n-1) = m-n+1

edges. This gives us

k = m-n+1

, confirming answer D. Let's examine why the other options fail. Option A gives

k = n-m+1

, which would be negative since

m > n

—but you can't reject a negative number of edges. Option B suggests

k = m-n

, which undercounts the rejected edges by 1, missing that trees need

n-1

edges, not

n

edges. Option C proposes

k = m-n-1

, which undercounts by 2, perhaps confusing the tree property or double-subtracting somewhere in the reasoning. The key insight is recognizing that "excess edges beyond tree requirement" means edges beyond the

n-1

needed for a spanning tree. Since we start with

m

edges and need

n-1

, we reject

m-(n-1) = m-n+1

edges. Study tip: Memorize that any tree on

n

vertices has exactly

n-1

edges. This relationship appears frequently in spanning tree, cycle detection, and connectivity problems.

Question 5

Consider applying Kruskal's algorithm to find a minimum spanning tree. At some intermediate step, we have already selected edges with weights $\{2, 3, 5, 7, 8\}$ and the next edges available (in order of increasing weight) are $\{9, 10, 11, 12\}$ . If selecting the edge of weight $9$ would create a cycle, which statement is necessarily true?

The edge of weight $10$ will definitely be included in the final MST
At least one edge from $\{10, 11, 12\}$ must be examined before completion (correct answer)
The current forest has exactly $6$ vertices distributed across multiple components
No more than $2$ additional edges will be needed to complete the MST

Explanation: Since 5 edges are selected and one more (weight 9) creates a cycle, we have at least 6 vertices. A spanning tree needs n-1 edges for n vertices, so we need at least 1 more edge. Since weight 9 is rejected, we must examine subsequent edges. Choice A is wrong because weight 10 might also create cycles. Choice C assumes exactly 6 vertices but we could have more. Choice D is wrong because we might need more than 2 additional edges if we have more than 7 vertices total.

Question 6

Consider running Kruskal's algorithm on a graph where some edges have equal weights. During execution, we encounter a situation where three edges $e_1, e_2, e_3$ all have weight $w$ and are the next candidates for selection. If selecting any two of these three edges would complete the MST, what must be true about the graph structure at this point?

The graph currently has exactly $3$ connected components, and edges $e_1, e_2, e_3$ each connect different pairs of these components (correct answer)
The graph currently has exactly $2$ connected components, and exactly $2$ of the edges $e_1, e_2, e_3$ connect these components while the third creates a cycle
The graph currently has exactly $4$ connected components, and edges $e_1, e_2, e_3$ form a triangle connecting three of these components
The graph currently has exactly $5$ connected components, and selecting any two edges reduces this to exactly $3$ components

Explanation: If selecting any two of three edges completes the MST, we need exactly 2 more edges to finish. This means we currently have exactly 3 components (since each edge reduces components by 1, and 3→2→1 requires 2 edges). The three edges must connect different pairs among these 3 components, and any 2 selections will connect all components. Choice B has wrong component count. Choice C would require 3 edges to connect 4 components. Choice D has incorrect component arithmetic.

Question 7

In a minimum spanning tree algorithm, the cut property states that for any cut of the graph, the minimum weight edge crossing the cut is guaranteed to be in some MST. However, this edge might not be in $every$ MST when there are multiple MSTs. Under what condition is the minimum weight edge crossing a cut guaranteed to be in $every$ MST?

When the cut is chosen such that one side contains exactly one vertex and that vertex has degree one
When the cut separates the graph into exactly two components of equal size in terms of vertex count
When the minimum weight edge crossing the cut is also the globally minimum weight edge in the entire graph
When the minimum weight edge crossing the cut has weight strictly less than all other edges crossing that same cut (correct answer)

Explanation: When analyzing minimum spanning trees (MSTs), you need to understand the distinction between "some MST" and "every MST." The cut property guarantees that the minimum weight edge crossing any cut appears in at least one MST, but when multiple edges share the same minimum weight across a cut, different MSTs might include different edges. The key insight is uniqueness. When the minimum weight edge crossing a cut has weight strictly less than all other edges crossing that same cut, there's no ambiguity—this edge is the only choice for connecting the two sides of the cut with minimum cost. Since every MST must connect these components and must do so optimally, every MST must include this unique minimum edge. Option A is wrong because vertex degree and cut size don't determine edge uniqueness across the cut. Option B incorrectly focuses on component sizes, which are irrelevant to edge weight uniqueness. Option C seems tempting, but being the global minimum edge doesn't guarantee uniqueness across a specific cut—there could still be multiple edges with the same global minimum weight crossing that cut. Option D correctly identifies that strict inequality (the edge weighs less than all others crossing the cut) ensures uniqueness. When there's only one minimum weight edge crossing a cut, every MST algorithm must select it. Study tip: In MST problems, always ask whether edges are unique. When weights are tied, multiple valid choices exist. When one edge is strictly better, it becomes mandatory in every optimal solution.

Question 8

Consider the following modification to Kruskal's algorithm: instead of always choosing the minimum weight edge that doesn't create a cycle, we choose the minimum weight edge that doesn't create a cycle AND has at least one endpoint with degree less than 3 in the current forest. If this modified algorithm produces a spanning tree, what can be concluded about the final tree?

The resulting spanning tree has exactly 3 vertices of degree 3, with all other vertices having degree ≤ 2
The resulting spanning tree is identical to the minimum spanning tree, since degree constraints don't affect optimality
The resulting spanning tree has maximum degree at most 3, and has total weight greater than or equal to the minimum spanning tree (correct answer)
The resulting spanning tree has maximum degree exactly 3, and may have total weight less than the minimum spanning tree

Explanation: When you encounter algorithm modifications like this, focus on how the constraint changes the algorithm's behavior and what guarantees remain intact. This modified Kruskal's algorithm adds a degree constraint: edges can only be added if at least one endpoint has degree less than 3. This directly limits the maximum degree of any vertex to 3, since once a vertex reaches degree 3, no more edges can be incident to it. The algorithm still follows the greedy approach of selecting minimum weight edges that don't create cycles, but with this additional restriction. Since we're adding constraints beyond the standard cycle-avoidance, the algorithm may be forced to skip some lighter edges that would violate the degree bound. This means the resulting tree's weight will be greater than or equal to the minimum spanning tree weight—it can't be better because we have fewer valid choices at each step. Choice A is incorrect because there's no guarantee that exactly 3 vertices will achieve degree 3. The constraint only provides an upper bound. Choice B is wrong because degree constraints absolutely can affect optimality—we might skip cheaper edges that would create high-degree vertices. Choice D incorrectly claims the maximum degree is exactly 3 (it could be less) and suggests the weight could be less than the MST (impossible when adding constraints). Choice C correctly identifies both key properties: maximum degree at most 3 (due to the degree constraint) and weight greater than or equal to the MST (due to the additional restriction limiting our edge choices). Study tip: When analyzing algorithm modifications, always ask: "What new constraints are added?" and "How do these constraints affect the solution quality compared to the original?"

Question 9

In Kruskal's algorithm applied to a weighted graph, edges are considered in the order: $(u_1,v_1)$ weight 2, $(u_2,v_2)$ weight 3, $(u_3,v_3)$ weight 3, $(u_4,v_4)$ weight 4, $(u_5,v_5)$ weight 5. If the algorithm accepts the first, second, and fourth edges but rejects the third and fifth edges, what can be concluded about the graph structure?

The third edge creates a cycle with the first two edges, and the fourth edge connects previously separate components (correct answer)
The third edge connects vertices already in the same component after adding the first two edges
The graph has exactly 4 vertices, and the spanning tree is completed after accepting the fourth edge
The fifth edge would create a cycle, but the third edge was rejected due to weight considerations only

Explanation: In Kruskal's algorithm, an edge is rejected if and only if it would create a cycle (i.e., both endpoints are already in the same connected component). Since the third edge

(u_3,v_3)

is rejected after accepting the first two, it means

(u_3,v_3)

would create a cycle with edges

(u_1,v_1)

and

(u_2,v_2)

. The fourth edge is accepted, meaning it connects two previously separate components. The fifth edge is rejected because by then we have a spanning tree (4 edges accepted implies 5 vertices, so we're done).

Question 10

In Prim's algorithm starting from vertex $s$ , the edges are added to the spanning tree in the order: $(s,a)$ weight 3, $(a,b)$ weight 5, $(s,c)$ weight 6, $(b,d)$ weight 4, $(c,e)$ weight 7. What is the minimum possible weight of edge $(a,c)$ in the original graph?

The edge $(a,c)$ can have any weight greater than 5, since it was not needed for connectivity
The edge $(a,c)$ must have weight at least 7, otherwise the algorithm would have chosen a different sequence
The edge $(a,c)$ must have weight greater than 6, otherwise it would have been selected instead of $(s,c)$ (correct answer)
The edge $(a,c)$ must have weight greater than 5, otherwise it would have been selected before $(s,c)$

Explanation: When analyzing Prim's algorithm execution, you need to understand that at each step, the algorithm selects the minimum-weight edge that connects a vertex in the growing tree to a vertex outside it. The key insight is determining when each edge could have been considered for selection. Let's trace through the algorithm. After adding

(s,a)

with weight 3, the tree contains vertices

\{s,a\}

. At this point, if edge

(a,c)

existed, it would be considered alongside

(a,b)

(weight 5) and

(s,c)

(weight 6) as potential next edges. Since

(a,b)

was chosen next, we know

(a,c)

must weigh at least 5. After adding

(a,b)

, the tree contains

\{s,a,b\}

. Now

(s,c)

(weight 6) was selected over

(a,c)

. This is the crucial moment: since

(a,c)

connects vertex

a

(in the tree) to vertex

c

(outside the tree), it was definitely considered. For

(s,c)

to be chosen instead,

(a,c)

must have weight greater than 6. Choice A is wrong because the weight does matter for the algorithm's decisions. Choice B incorrectly states the threshold as 7, but the comparison was against

(s,c)

's weight of 6, not

(c,e)

's weight of 7. Choice D uses the wrong threshold of 5, which would only ensure

(a,c)

wasn't chosen before

(a,b)

, not before

(s,c)

. Choice C correctly identifies that

(a,c)

must weigh more than 6 to explain why

(s,c)

was selected when both edges were available. Study tip: In Prim's algorithm problems, always identify exactly when each edge becomes "available" and what it was competing against at that moment.

Question 11

A graph $G$ has the property that removing any single edge results in exactly two connected components, each of which is a tree. How many spanning trees does $G$ have?

Graph $G$ has exactly 2 spanning trees, obtained by removing either of two specific edges
Graph $G$ has exactly $n-1$ spanning trees where $n$ is the number of vertices in $G$
Graph $G$ has exactly 1 spanning tree, since $G$ itself must be a tree with one extra edge
Graph $G$ has exactly $n$ spanning trees where $n$ is the number of edges in $G$ (correct answer)

Explanation: When you encounter a graph problem describing what happens when edges are removed, you're dealing with connectivity and spanning tree concepts. The key insight is understanding what type of graph structure satisfies the given condition. If removing any single edge from graph

G

creates exactly two connected components that are both trees, then

G

must be a connected graph with exactly one cycle. Here's why: a connected graph with no cycles is already a tree, so removing any edge would disconnect it into exactly two tree components. But if

G

had multiple cycles, removing a single edge from outside those cycles wouldn't necessarily create the described pattern. A connected graph with exactly one cycle has a special property: it has exactly

n

spanning trees, where

n

is the number of edges (which equals the number of vertices in this case). Each spanning tree is obtained by removing exactly one edge from the unique cycle, and there are

n

edges total. Answer A is incorrect because you can remove any of the

n

edges in the cycle, not just two specific edges. Answer B confuses the relationship—while

n-1

is the number of edges in any spanning tree, it's not the count of how many spanning trees exist. Answer C reflects the misconception that having "one extra edge" beyond a tree structure means only one spanning tree exists, but this ignores that you can remove any edge from the cycle. Remember: when a graph has exactly one cycle, the number of spanning trees equals the cycle length, which equals the total number of edges in the graph.

Question 12

A minimum spanning tree algorithm is run on a connected graph with distinct edge weights. The algorithm produces a spanning tree $T$ with total weight 45. If the heaviest edge in $T$ has weight 12, what can be definitively concluded?

Every spanning tree of this graph has total weight 45, and contains the edge of weight 12
There exists no spanning tree of this graph with total weight less than 45 (correct answer)
Every spanning tree of this graph contains the edge of weight 12 as its heaviest edge
Any other spanning tree of this graph has total weight greater than 45 and heaviest edge weight ≥ 12

Explanation: Since the edge weights are distinct and a minimum spanning tree algorithm was used, the resulting tree T is the unique minimum spanning tree. Therefore, no spanning tree can have total weight less than 45. However, we cannot conclude that every spanning tree contains the edge of weight 12 (option A), as other spanning trees might exclude this edge and include heavier edges. Option C is wrong because other spanning trees might have heavier edges than 12. Option D is wrong because while other trees will have total weight > 45, their heaviest edge could potentially be lighter than 12 if they use many medium-weight edges instead of the particular combination in T.

Question 13

A weighted graph $G$ has the property that its minimum spanning tree is unique, but if any edge weight is increased by 1, the minimum spanning tree is no longer unique. What does this imply about the edge weights in $G$ ?

All edges in the original minimum spanning tree have the same weight as some edge not in the tree
The minimum spanning tree contains at least one edge whose weight equals the weight of an edge not in the tree
Every edge in the minimum spanning tree has weight exactly 1 less than some edge not in the tree
There exists an edge not in the minimum spanning tree whose weight equals the weight of the heaviest edge in the tree (correct answer)

Explanation: When analyzing minimum spanning trees (MSTs) and uniqueness conditions, you need to understand what makes an MST unique and how small weight changes affect this uniqueness. An MST is unique when no two edges have the same weight, or more precisely, when there's no "tie-breaking" situation during construction. The key insight here is that if increasing any edge weight by 1 makes the MST non-unique, then the original graph was right at the boundary of uniqueness. Consider what happens when you increase an edge weight by 1. If this creates non-uniqueness, it means you've created a situation where two different spanning trees now have the same total weight. This can only occur if there was previously an edge outside the MST whose weight equaled the weight of the heaviest edge in the MST. When you increase any edge weight by 1, you either make the MST heavier (if you increased an edge in the MST) or create the possibility of an alternative MST with the same weight. Choice A is too broad—not all MST edges need this property, just one. Choice B is close but doesn't specify which edge matters most. Choice C incorrectly suggests a systematic 1-unit difference, which isn't required. Choice D correctly identifies that there must exist an edge outside the MST whose weight equals the heaviest MST edge weight—this creates the critical balance point. Study tip: For MST uniqueness problems, focus on the heaviest edges and look for weight equalities between MST and non-MST edges. These create the "breaking points" where uniqueness changes.

Question 14

Consider a connected graph where every edge has a distinct weight. If edge $e$ is the heaviest edge in some cycle $C$ , what can be concluded about $e$ 's inclusion in the minimum spanning tree?

Edge $e$ cannot be included in any minimum spanning tree of the graph (correct answer)
Edge $e$ may or may not be in the MST, depending on weights of edges outside cycle $C$
Edge $e$ will be included in the MST unless it is the globally heaviest edge in the entire graph
Edge $e$ will be included in the MST if and only if removing it disconnects the graph

Explanation: This follows from the cycle property of MSTs: if e is the heaviest edge in cycle C, then e cannot be in any MST. This is because we could remove e and add any other edge from C to get a spanning tree with smaller total weight. The distinctness of weights ensures this conclusion is definitive. Choice B is wrong because edges outside C don't affect this property. Choice C is wrong because being the global heaviest isn't necessary. Choice D confuses the cycle property with bridge characterization.

Question 15

In a weighted graph, Prim's algorithm is being executed starting from vertex $v$ . After $k$ iterations, the algorithm has selected a set $S$ of edges. Which statement about $S$ is always true?

$S$ contains the $k$ globally lightest edges that form a connected subgraph including $v$
$S$ forms a tree that includes $v$ and represents the minimum spanning tree of the induced subgraph
$S$ contains $k$ edges that form a tree connecting $k+1$ vertices including $v$ (correct answer)
$S$ includes every edge that is lightest among all edges crossing some cut of the graph

Explanation: Prim's algorithm maintains a tree at each step, adding exactly one vertex per iteration. After k iterations, we have k edges connecting k+1 vertices (including the starting vertex v). Choice A is wrong because Prim's doesn't necessarily select globally lightest edges, only lightest edges crossing the current cut. Choice B is wrong because S represents the MST of the vertices selected so far, not of some induced subgraph. Choice D is wrong because not every lightest cut edge is included, only those that extend the current tree.

Question 16

A minimum spanning tree of a weighted graph $G$ has total weight $W$ . If all edge weights in $G$ are increased by a constant $c > 0$ , what can be concluded about the new minimum spanning tree?

The new MST will have the same structure as the original, with total weight $W + c$
The new MST will have the same structure as the original, with total weight $W + c(n-1)$ where $n$ is the number of vertices (correct answer)
The new MST may have different structure, but will have total weight $W + c(n-1)$ where $n$ is the number of vertices
The new MST may have different structure, but will have total weight $W + c(m)$ where $m$ is the number of edges

Explanation: Adding a constant c to all edge weights preserves the relative ordering of edges, so the same MST structure is optimal. Since an MST has exactly n-1 edges (where n is the number of vertices), the total weight increases by c(n-1). Choice A incorrectly adds c only once instead of c times the number of MST edges. Choice C correctly calculates weight but wrongly suggests structure might change. Choice D uses the wrong multiplier (total edges instead of MST edges) and suggests structure might change.