You are running Kruskal's algorithm. You've already added several edges to your MST. The next-lightest remaining edge connects vertex A to vertex B, but both A and B are already in your current tree. What should you do?
AAdd it anyway — Kruskal's always adds the globally lightest available edge.
BSkip it, because adding it would create a cycle in the spanning tree.
CReplace the heaviest edge currently in the tree with this lighter one.
DStop the algorithm — encountering this edge means the MST is complete.
A spanning tree by definition contains no cycles. If A and B are already connected through the current tree, adding another edge between them would create a cycle — violating the tree property. Kruskal's adds edges greedily in weight order BUT only if they don't create a cycle. This cycle-detection step is the key operation, implemented via Union-Find in practice. The algorithm is not done — it continues until n−1 edges have been added.
Question 2 Multiple Choice
Why can Kruskal's and Prim's algorithms find globally optimal MSTs using only local greedy choices, while a greedy approach fails for minimum Hamiltonian paths?
ABecause MST algorithms process a smaller number of edges than Hamiltonian path algorithms.
BBecause the cut property provides a local certificate of global optimality: the minimum-weight edge crossing any partition of vertices into two sets must belong to some MST.
CBecause spanning trees are structurally simpler than Hamiltonian paths, making search space exploration easier.
DBecause greedy algorithms are universally correct for graph problems and fail only for non-graph combinatorial problems.
The cut property is the structural reason greedy works for MSTs: for any way you divide the graph's vertices into two groups, the cheapest edge crossing that cut must appear in some MST. This means every locally greedy choice has a global guarantee. The minimum Hamiltonian path problem lacks this property — adding the locally cheapest edge can foreclose globally optimal solutions. MST belongs to a matroid structure where local optima are global; TSP does not.
Question 3 True / False
A weighted connected graph typically has exactly one minimum spanning tree.
TTrue
FFalse
Answer: False
When two or more edges have equal weights, different spanning trees can be constructed that each achieve the same minimum total weight. For example, if edges (A,B) and (C,D) both weigh 5, and either could be included in a valid MST, there may be multiple MSTs all sharing the same optimal cost. Uniqueness is only guaranteed when all edge weights are distinct. This is explicitly noted as a common misconception in the topic.
Question 4 True / False
According to the cut property, the minimum-weight edge crossing any partition of a connected graph's vertices into two non-empty sets must belong to at least one MST.
TTrue
FFalse
Answer: True
The cut property is the foundational theorem underlying both Kruskal's and Prim's correctness. For any cut (partition of vertices into two non-empty sets), the lightest edge crossing it is guaranteed to appear in some MST. Prim's algorithm exploits this directly at every step: it grows a tree by always adding the cheapest edge from the current tree to an outside vertex — which is always the minimum-weight edge crossing the cut between 'inside' and 'outside' vertices.
Question 5 Short Answer
A network designer installs cables connecting 10 cities using exactly the MST of the city graph. Several months later, one cable fails (an edge is removed from the MST). Why does this necessarily disconnect at least two cities from the rest? How does this relate to the defining structural property of spanning trees?
Think about your answer, then reveal below.
Model answer: A spanning tree has exactly n−1 edges and, crucially, no cycles. This means there is exactly one path between any pair of vertices. When an edge is removed from a tree, the unique path between the vertices it connected is eliminated — the tree splits into two disconnected components. There is no redundant path to fall back on. This is why the designer's choice of the MST, while cost-optimal, provides zero fault tolerance: any single edge failure disconnects the network. The tradeoff between cost minimization (MST) and redundancy (additional edges) is a core network design consideration.
The key structural insight is that trees are minimally connected: they use the fewest possible edges (n−1) to keep all vertices reachable, which also means removing any single edge breaks connectivity. MST minimizes cost by exploiting this minimality — but minimality means no redundancy.