Discrete Math Quiz: Kruskals And Prims Algorithms
18 questions · exam conditions
0:00
Kruskals And Prims AlgorithmsQuestion 1 of 18

In Prim's algorithm, suppose the current tree contains vertices {A,B,C} and we're deciding between edges (A,D):5, (B,E):5, and (C,F):7. A student argues we should choose (C,F):7 because "vertex F hasn't been visited yet, while D and E might have been considered before." What's the flaw in this reasoning?

The reasoning is correct - Prim's algorithm prioritizes previously unconsidered vertices to ensure coverage
Prim's algorithm requires selecting the vertex with the highest alphabetical label when weights are equal
The reasoning fails because vertex F is actually farther from the starting vertex than D or E
Prim's algorithm chooses edges based solely on weight, not on whether vertices were previously considered
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Kruskals And Prims Algorithms

Practice Kruskals And Prims Algorithms 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 Kruskals And Prims Algorithms, 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

In Prim's algorithm, suppose the current tree contains vertices {A,B,C} and we're deciding between edges (A,D):5, (B,E):5, and (C,F):7. A student argues we should choose (C,F):7 because "vertex F hasn't been visited yet, while D and E might have been considered before." What's the flaw in this reasoning?

  1. The reasoning is correct - Prim's algorithm prioritizes previously unconsidered vertices to ensure coverage
  2. Prim's algorithm requires selecting the vertex with the highest alphabetical label when weights are equal
  3. The reasoning fails because vertex F is actually farther from the starting vertex than D or E
  4. Prim's algorithm chooses edges based solely on weight, not on whether vertices were previously considered (correct answer)
Explanation: When you encounter questions about Prim's algorithm, remember that it's a greedy algorithm focused exclusively on building the minimum spanning tree by always selecting the lightest available edge that connects the current tree to a new vertex. Prim's algorithm operates with a simple rule: from all edges that connect your current tree to vertices not yet in the tree, always choose the one with the smallest weight. In this case, you have three options connecting tree {A,B,C} to new vertices: (A,D):5, (B,E):5, and (C,F):7. Since edges to D and E both have weight 5 (lighter than the weight-7 edge to F), either would be a valid choice. The algorithm would typically break ties using a consistent method like alphabetical order, making (A,D) the selection. Let's examine why each incorrect option fails: Choice A incorrectly suggests Prim's prioritizes "coverage" of unconsidered vertices, but Prim's only cares about edge weights. Choice B makes up a non-existent rule about alphabetical vertex labels when weights are equal—while implementations may use alphabetical ordering to break ties, this isn't a requirement of the algorithm itself. Choice C introduces the irrelevant concept of distance from the starting vertex, but Prim's doesn't track or consider distances to the starting point. Choice D correctly identifies that Prim's algorithm makes decisions based purely on edge weights, ignoring whether vertices were previously considered or any other factors. Study tip: Remember that greedy algorithms like Prim's follow their optimization criterion religiously—for Prim's, that's always "smallest weight edge that grows the tree."

Question 2

During Kruskal's algorithm on a graph with 7 vertices, we process edges in this order: accept (A,B):2, accept (C,D):3, reject (A,C):4, accept (E,F):4, reject (B,D):5, accept (A,E):6. At this point, how many more edges do we need to complete the MST, and what caused the rejections?

  1. Need 2 more edges; rejections occurred because those edges had weights larger than previously accepted edges
  2. Need 3 more edges; rejections occurred because those edges would have created cycles in the forest
  3. Need 2 more edges; rejections occurred because those edges would have created cycles in the forest (correct answer)
  4. Need 2 more edges; rejections occurred because those edges connected vertices already in the same component
Explanation: When you encounter Kruskal's algorithm questions, focus on two key principles: we're building a minimum spanning tree by adding edges in weight order, and we must avoid creating cycles. Let's trace through this step-by-step. In Kruskal's algorithm, we need exactly n−1=6n-1 = 6 edges for a complete MST with 7 vertices. So far, we've accepted 4 edges: (A,B), (C,D), (E,F), and (A,E). This means we need 6−4=26-4 = 2 more edges to complete the MST. Now for the rejections: When we rejected (A,C) with weight 4, vertices A and B were already connected, and C and D were connected, but these were separate components, so adding (A,C) wouldn't create a cycle. However, when we later accepted (A,E), this connected the A-B component with E-F. At the point we rejected (B,D), vertices B and D were in different components of our forest, so this rejection must have occurred because it would create a cycle within the existing structure. Answer A is wrong because edge rejection in Kruskal's isn't based on weight comparison with previous edges—we process edges in sorted weight order regardless. Answer B incorrectly states we need 3 more edges when we clearly need only 2. Answer D uses imprecise language; while "same component" sounds similar to cycle detection, the specific reason for rejection in Kruskal's is cycle prevention. Remember: In Kruskal's algorithm questions, always count accepted edges to determine remaining needs, and remember that rejections occur specifically to prevent cycles in the growing forest structure.

Question 3

During Kruskal's algorithm execution on a graph with 6 vertices, we've added edges with weights 2, 3, 4, and 6 in that order. The algorithm now considers an edge of weight 7. If this edge is rejected, what's the minimum number of edges we must examine before finding the next edge to add?

  1. Exactly 1 more edge, since we need exactly 1 more edge to complete the MST
  2. At least 2 more edges, since we need 2 more edges to span all 6 vertices
  3. Exactly 0 more edges, since we already have a complete spanning tree with 4 edges
  4. At least 1 more edge, but possibly several if multiple edges create cycles (correct answer)
Explanation: Kruskal's algorithm builds a minimum spanning tree by adding edges in order of increasing weight, rejecting any edge that would create a cycle. Understanding where you are in the algorithm's progress is crucial for predicting what happens next. With 6 vertices, a complete spanning tree requires exactly 6−1=56-1 = 5 edges. You've successfully added 4 edges (weights 2, 3, 4, 6), so you need exactly 1 more edge to complete the MST. The edge of weight 7 was rejected because it would create a cycle with the existing 4 edges. Since you need 1 more edge and the weight-7 edge was rejected, you must examine additional edges until you find one that doesn't create a cycle. You're guaranteed to eventually find such an edge (since the graph must be connected to have an MST), but there's no way to predict how many edges you'll need to examine first. Multiple consecutive edges might all create cycles before you find the final valid edge. Answer choice A incorrectly assumes the very next edge will definitely be accepted. Answer choice B makes an error about how many edges remain needed - you need exactly 1 more, not 2 more. Answer choice C completely misunderstands the situation, thinking 4 edges somehow complete a spanning tree for 6 vertices. The correct answer is D because you definitely need at least 1 more edge, but potentially several more if consecutive edges create cycles. Study tip: In Kruskal's algorithm problems, always track two things: how many edges you need total (n−1n-1 for nn vertices) and remember that rejected edges tell you about cycles, not about completion.

Question 4

During Kruskal's algorithm execution, we've processed edges in order: (A,B):2, (C,D):3, (B,E):4, (D,F):5. The next lightest edge is (A,C):6. If adding (A,C) would create a cycle, what can we conclude about the current forest structure?

  1. Vertices A and C are already connected through the path A-B-E-D-C in some order
  2. Vertices A and C must be in the same connected component of the current forest (correct answer)
  3. Edge (A,C) was already added earlier with a different weight value
  4. The algorithm has made an error since Kruskal's never encounters cycles
Explanation: In Kruskal's algorithm, adding an edge creates a cycle if and only if both endpoints are already in the same connected component of the current forest. Since adding (A,C) would create a cycle, A and C must already be connected through some path in the forest. Choice A specifies a particular path that may not exist. Choice C is impossible - each edge is considered only once. Choice D is wrong - Kruskal's specifically checks for and avoids cycles.

Question 5

In Kruskal's algorithm applied to a connected graph, suppose we've processed all edges of weight 1, 2, and 3, and our forest currently has 3 connected components. The next lightest edges all have weight 4. What's the minimum number of weight-4 edges that must be added to ensure the forest becomes connected?

  1. Exactly 2 edges, since we need to merge 3 components into 1 component (correct answer)
  2. At least 2 edges, but possibly more if some weight-4 edges create cycles within components
  3. Exactly 3 edges, since each component needs at least one connection to other components
  4. At least 1 edge, since any edge between different components will start the merging process
Explanation: To merge 3 connected components into 1 component, we need exactly 2 edges. Each edge can merge at most 2 components, so going from 3 components to 1 requires exactly 2 merging operations. Since we're in Kruskal's algorithm and the graph is connected, there must exist edges between different components. Choice B is wrong because weight-4 edges within components would have been rejected (create cycles), so all weight-4 edges considered must connect different components. Choice C overcounts. Choice D undercounts the number needed.

Question 6

Two students implement Prim's algorithm on the same graph, both starting from vertex A. Student 1 uses a priority queue that extracts minimum elements, while Student 2 uses a regular queue (FIFO). Student 2 claims their approach is equivalent because "we can just add edges to the queue in sorted order initially." What's the fundamental flaw in Student 2's approach?

  1. Student 2's approach will work correctly if all edges are pre-sorted, producing the same MST as Student 1
  2. Student 2's approach fails because FIFO order doesn't guarantee minimum-weight edge selection even with pre-sorting
  3. Student 2's approach fails because new edges become available as vertices are added to the tree during execution (correct answer)
  4. Student 2's approach works for small graphs but fails for larger graphs due to memory constraints of the FIFO queue
Explanation: When analyzing graph algorithms like Prim's, you need to understand how they dynamically discover new possibilities as they build the solution. Prim's algorithm grows a minimum spanning tree by repeatedly selecting the lightest edge that connects a vertex already in the tree to a vertex not yet included. The correct answer is C because Prim's algorithm is inherently dynamic - as you add each new vertex to your growing tree, that vertex brings with it new edges that weren't previously available for consideration. You can't know all possible edges at the start because you don't know which vertices will be added in what order. When vertex v joins the tree, all edges from v to unexplored vertices suddenly become candidates for the next selection. A FIFO queue with pre-sorted edges cannot adapt to these newly available options during execution. Option A is wrong because even with perfect pre-sorting, a FIFO queue cannot handle the dynamic edge discoveries that occur as the algorithm progresses. Option B misses the main issue - while FIFO order is indeed problematic, the deeper problem isn't just about order, but about the algorithm's dynamic nature. Option D incorrectly focuses on memory constraints, which aren't the fundamental algorithmic issue here. The key insight is that Prim's algorithm requires a priority queue precisely because the set of candidate edges changes as the algorithm runs. You need to continuously re-evaluate which available edge has minimum weight among the current possibilities, not just process a predetermined list.

Question 7

A graph has an MST of total weight 20. A student runs Kruskal's algorithm but accidentally processes edge (X,Y) with weight 8 before edge (P,Q) with weight 6, even though they should be processed in weight order. If both edges end up in the final spanning tree, what can we conclude?

  1. The algorithm produced a suboptimal spanning tree with weight greater than 20 due to the ordering error
  2. The spanning tree is optimal, but we cannot determine if its weight is 20 without more information
  3. The algorithm failed because Kruskal's requires strict weight ordering to function correctly
  4. The algorithm still produced an optimal MST of weight 20 despite the ordering error (correct answer)
Explanation: This question tests your understanding of how Kruskal's algorithm works and why it produces optimal results. The key insight is that Kruskal's algorithm is greedy but robust — it builds an MST by adding the lightest available edge that doesn't create a cycle, and this approach guarantees optimality regardless of small ordering mistakes. When you process edges out of perfect weight order but both edges end up in the final spanning tree, it means both edges were genuinely needed to connect different components of the graph. Since an MST requires exactly n−1n-1 edges to connect nn vertices, and Kruskal's only accepts edges that don't form cycles, any edge that gets accepted is necessary for connectivity. The order in which you process edges of different weights doesn't matter as long as you're still following the "no cycles" rule. Choice A is wrong because processing edges slightly out of order doesn't compromise optimality when both edges are needed. Choice B incorrectly suggests uncertainty about the weight — if both edges are required and the original MST weight was 20, this spanning tree must also weigh 20. Choice C misunderstands how Kruskal's works; while strict ordering is the standard procedure, minor deviations don't break the algorithm if you still avoid cycles. The correct answer is D: the algorithm still produced an optimal MST of weight 20. Study tip: Remember that Kruskal's fundamental rule is "add the lightest edge that doesn't create a cycle." As long as you follow this rule, you'll get an optimal MST even with minor ordering errors between edges of different weights.

Question 8

In Prim's algorithm, suppose we start with vertex A and the current partial tree contains vertices {A, B, C}. The algorithm must next choose among edges (C,D) with weight 4, (B,E) with weight 6, and (A,F) with weight 3. However, there's also edge (B,C) with weight 2. Why isn't (B,C) considered?

  1. Edge (B,C) has already been added to connect B and C to the tree
  2. Edge (B,C) would create a cycle since both endpoints are in the current tree (correct answer)
  3. Edge (B,C) violates Prim's requirement that edges must connect to vertex A
  4. Edge (B,C) has weight 2, which is too small for Prim's algorithm
Explanation: Prim's algorithm only considers edges that connect a vertex in the current tree to a vertex outside the tree. Since both B and C are already in the partial tree {A,B,C}, edge (B,C) would create a cycle and is not considered. Choice A is incorrect because (B,C) may not have been the edge used to add these vertices. Choice C misunderstands Prim's - edges don't need to connect to the starting vertex. Choice D is nonsensical - smaller weights are preferred.

Question 9

Consider a graph where Prim's algorithm starting from vertex S produces the sequence of edges: (S,A):3, (A,B):2, (S,C):4, (C,D):1. A student claims this sequence is impossible because "Prim's should have chosen (C,D):1 earlier since it has the smallest weight." What's wrong with the student's reasoning?

  1. The student is correct - Prim's algorithm would choose (C,D):1 first among all edges in the graph
  2. Prim's algorithm must maintain alphabetical order of vertices, so D cannot be added before B
  3. Edge (C,D):1 was not available for selection until vertex C was added to the tree in step 3 (correct answer)
  4. The sequence is impossible because Prim's cannot select (S,C):4 when (A,B):2 has smaller weight
Explanation: When analyzing Prim's algorithm sequences, remember that this greedy algorithm builds a minimum spanning tree by adding one vertex at a time, always selecting the minimum-weight edge that connects a vertex already in the tree to a vertex not yet in the tree. The key insight here is that Prim's algorithm can only consider edges that have one endpoint in the current tree and one endpoint outside it. Let's trace through the given sequence: Starting from S, we can only choose edges connected to S. After adding A with edge (S,A):3, we can now consider edges from both S and A. The algorithm selects (A,B):2, then (S,C):4. Crucially, edge (C,D):1 couldn't be selected earlier because vertex C wasn't in the tree yet - the algorithm had no way to "see" or consider this edge until C was added in step 3. Choice A incorrectly assumes Prim's considers all edges in the graph simultaneously, but the algorithm only evaluates edges connected to the current tree. Choice B invents a non-existent alphabetical ordering rule - Prim's algorithm has no such constraint and only cares about edge weights among available choices. Choice D misunderstands the selection process by comparing (S,C):4 with (A,B):2, but these edges weren't competing against each other since they were selected in different steps when different edge sets were available. Remember: Prim's algorithm is constrained by connectivity, not just weight. An edge can only be selected when exactly one of its endpoints is already in the growing tree.

Question 10

Consider applying Kruskal's algorithm to a graph where the edges, sorted by weight, are: (A,B):1, (C,D):2, (A,C):3, (B,D):4, (A,D):5, (B,C):6. After processing the first four edges in order, how many connected components remain in the forest?

  1. One connected component, since all vertices are now connected in a single tree (correct answer)
  2. Two connected components, since edge (B,D):4 was rejected for creating a cycle
  3. Three connected components, since only two edges were actually added to the forest
  4. Four connected components, since each vertex still forms its own separate component
Explanation: Processing in order: (A,B):1 connects A and B. (C,D):2 connects C and D. We have components {A,B} and {C,D}. (A,C):3 connects these components, forming {A,B,C,D}. (B,D):4 would create a cycle since B and D are already connected through B-A-C-D, so it's rejected. After these four edges, all vertices A,B,C,D are in one component. Choice B incorrectly thinks rejection of (B,D) leaves components separate. Choice C undercounts added edges. Choice D ignores that edges were added.

Question 11

A graph has edges with weights forming an arithmetic sequence: 2,4,6,8,10,122, 4, 6, 8, 10, 12. When Kruskal's algorithm is applied, it accepts edges with weights 2,4,8,102, 4, 8, 10 and rejects edges with weights 6,126, 12. Based on this information, which statement about applying Prim's algorithm to the same graph is most likely correct?

  1. Prim's algorithm will accept the same set of edges regardless of the starting vertex chosen
  2. Prim's algorithm might accept the edge with weight 6 instead of another edge to achieve the same optimal total weight (correct answer)
  3. Prim's algorithm will definitely reject the edge with weight 6 since Kruskal's rejected it
  4. Prim's algorithm will produce a spanning tree with different total weight than Kruskal's algorithm
Explanation: Both algorithms must find minimum spanning trees with the same total weight, but they may select different edges when multiple MSTs exist. The edge with weight 6 was rejected by Kruskal's because it would create a cycle, but Prim's algorithm might encounter it at a point where it can be included instead of another edge, still achieving the optimal total weight.

Question 12

A complete graph K4K_4 has vertices {A,B,C,D}\{A,B,C,D\} with edge weights: (A,B):1(A,B):1, (A,C):4(A,C):4, (A,D):5(A,D):5, (B,C):2(B,C):2, (B,D):6(B,D):6, (C,D):3(C,D):3. When applying Prim's algorithm starting from vertex AA, what is the second edge added to the spanning tree?

  1. Edge (A,C):4(A,C):4 because it connects AA to the next closest vertex after BB
  2. Edge (B,C):2(B,C):2 because it has minimum weight among edges from {A,B}\{A,B\} to {C,D}\{C,D\} (correct answer)
  3. Edge (C,D):3(C,D):3 because it will eventually be needed and has relatively low weight
  4. Edge (A,D):5(A,D):5 because the algorithm systematically explores from the starting vertex AA
Explanation: Prim's algorithm starts with vertex AA. First, it adds the minimum weight edge from AA, which is (A,B):1(A,B):1. Now the tree contains {A,B}\{A,B\}. For the second edge, it considers all edges from {A,B}\{A,B\} to {C,D}\{C,D\}: (A,C):4(A,C):4, (A,D):5(A,D):5, (B,C):2(B,C):2, (B,D):6(B,D):6. The minimum is (B,C):2(B,C):2.

Question 13

During the execution of Prim's algorithm on a weighted graph, at some intermediate step, the current tree contains vertices {A,C,D}\{A, C, D\} and the algorithm must choose the next edge to add. The candidate edges from the current tree to vertices not yet included are: (A,B)(A,B) with weight 6, (C,E)(C,E) with weight 4, (D,B)(D,B) with weight 6, and (D,F)(D,F) with weight 7. After adding the next edge, which statement about the subsequent step is necessarily true?

  1. The algorithm will next consider edge (E,F)(E,F) if it exists and has the minimum weight among new candidates
  2. The algorithm will have exactly 4 candidate edges to choose from in the next iteration
  3. The algorithm will next add whichever edge has minimum weight among all edges incident to vertex EE
  4. The algorithm will consider all edges from vertices {A,C,D,E}\{A,C,D,E\} to vertices not yet in the tree (correct answer)
Explanation: Prim's algorithm will add edge (C,E)(C,E) with weight 4 since it has minimum weight. In the next step, the tree contains {A,C,D,E}\{A,C,D,E\} and the algorithm considers all edges from these vertices to vertices not yet in the tree, choosing the minimum weight among all such edges.

Question 14

In Kruskal's algorithm, edges are processed in order: (A,B):2(A,B):2, (C,D):3(C,D):3, (B,E):4(B,E):4, (A,C):4(A,C):4, (D,F):5(D,F):5, (E,F):6(E,F):6, (B,C):7(B,C):7. At what point during the algorithm's execution are there exactly two connected components remaining?

  1. After processing edge (C,D):3(C,D):3 but before processing edge (B,E):4(B,E):4
  2. After processing edge (B,E):4(B,E):4 but before processing edge (A,C):4(A,C):4
  3. After processing edge (A,C):4(A,C):4 but before processing edge (D,F):5(D,F):5 (correct answer)
  4. After processing edge (D,F):5(D,F):5 but before processing edge (E,F):6(E,F):6
Explanation: Initially we have 6 components: {A},{B},{C},{D},{E},{F}\{A\}, \{B\}, \{C\}, \{D\}, \{E\}, \{F\}. After (A,B):2(A,B):2: 5 components. After (C,D):3(C,D):3: 4 components. After (B,E):4(B,E):4: 3 components {A,B,E},{C,D},{F}\{A,B,E\}, \{C,D\}, \{F\}. After (A,C):4(A,C):4: 2 components {A,B,C,D,E},{F}\{A,B,C,D,E\}, \{F\}. So exactly 2 components exist after processing (A,C):4(A,C):4.

Question 15

Consider applying Prim's algorithm starting from vertex SS to find a minimum spanning tree. At some point during execution, the algorithm has built a tree TT and is choosing between edges (u,v)(u,v) and (w,x)(w,x), both with weight 5, where u,w∈Tu,w \in T and v,x∉Tv,x \notin T. The algorithm selects (u,v)(u,v). In the very next iteration, what determines which edge the algorithm will select?

  1. The minimum weight edge among all edges from {u,v}\{u,v\} to vertices not in the current tree
  2. The minimum weight edge among all edges from vertices in T∪{v}T \cup \{v\} to vertices not in the current tree (correct answer)
  3. The edge (w,x)(w,x) will definitely be selected since it was the runner-up in the previous iteration
  4. The minimum weight edge among all edges incident to the newly added vertex vv
Explanation: Prim's algorithm maintains a cut between vertices in the current tree and vertices not yet included. After adding vertex vv, the tree becomes T∪{v}T \cup \{v\}, and the algorithm selects the minimum weight edge crossing the cut from any vertex in T∪{v}T \cup \{v\} to any vertex not in the tree. This includes reconsidering (w,x)(w,x) and any new edges from vv.

Question 16

During Kruskal's algorithm execution on a graph with 7 vertices, the algorithm has processed some edges and currently has 3 connected components: {A,B,C}\{A,B,C\}, {D,E}\{D,E\}, and {F,G}\{F,G\}. The next three edges in order of increasing weight are: (A,D):10(A,D):10, (B,F):10(B,F):10, (C,E):11(C,E):11. After processing these three edges, how many edges will the final minimum spanning tree contain?

  1. 6 edges total, since any spanning tree of 7 vertices requires exactly 6 edges (correct answer)
  2. 5 edges total, since we started with 3 components and need 2 more edges to connect them
  3. 7 edges total, since we process 3 more edges and had some edges already processed
  4. 4 edges total, since we had 4 edges to create the current components plus 2 more needed
Explanation: A spanning tree of any graph with nn vertices always contains exactly n−1n-1 edges. Since this graph has 7 vertices, its spanning tree must contain exactly 6 edges, regardless of how the algorithm processes them or how many components exist at any intermediate step. The number of edges in the final spanning tree is determined solely by the number of vertices.

Question 17

Consider a weighted graph where Kruskal's algorithm processes edges in this order and makes these decisions: (A,B):3(A,B):3 - accept, (C,D):3(C,D):3 - accept, (B,C):4(B,C):4 - accept, (A,D):5(A,D):5 - reject, (D,E):6(D,E):6 - accept, (C,E):7(C,E):7 - reject. What can be concluded about the structure of this graph?

  1. The graph has exactly 5 vertices and the algorithm successfully found a minimum spanning tree (correct answer)
  2. The graph contains a cycle involving vertices A,B,C,DA, B, C, D and another involving C,D,EC, D, E
  3. The algorithm rejected (A,D):5(A,D):5 incorrectly since it has lower weight than (D,E):6(D,E):6
  4. The graph must have additional vertices beyond {A,B,C,D,E}\{A,B,C,D,E\} since only 4 edges were accepted
Explanation: The algorithm accepted 4 edges for a graph with 5 vertices, which is correct for a spanning tree (n−1n-1 edges). Edge (A,D):5(A,D):5 was rejected because accepting it would create a cycle in the path A−B−C−D−AA-B-C-D-A. Edge (C,E):7(C,E):7 was rejected because CC and EE were already connected through the path C−B−A−D−EC-B-A-D-E. The algorithm worked correctly.

Question 18

A connected graph has 8 vertices and 12 edges. When applying Kruskal's algorithm to find a minimum spanning tree, at what point in the algorithm will the next edge addition create the spanning tree?

  1. After adding the 6th edge to the forest
  2. After adding the 7th edge to the forest (correct answer)
  3. After adding the 8th edge to the forest
  4. After adding the 5th edge to the forest
Explanation: A spanning tree for n vertices has exactly n-1 edges. With 8 vertices, the MST needs 7 edges. Kruskal's algorithm adds edges one by one, so after adding the 7th edge, we have the complete spanning tree. Choice A (6th edge) leaves us with 6 edges, which is incomplete. Choice C (8th edge) would create a cycle. Choice D (5th edge) gives only 5 edges, far from complete.