Kruskal's algorithm for minimum spanning tree always adds the cheapest edge that does not create a cycle. Why does this greedy strategy provably yield an optimal solution?
ASpanning trees have a unique structure that makes local choices globally optimal
BThe edge set of a graph forms a graphic matroid, and the greedy algorithm is provably optimal on any matroid
CKruskal's algorithm uses dynamic programming to ensure global optimality, not pure greedy selection
DThe algorithm works because minimum spanning trees are always unique for graphs with distinct edge weights
Kruskal's algorithm is a greedy algorithm: at each step, add the cheapest available element that preserves independence (no cycles). The reason it is provably optimal is that the forests of a graph form a graphic matroid — the exchange axiom holds, so all maximal independent sets (spanning forests) have the same size. The matroid greedy theorem guarantees that greedy finds a maximum-weight basis in any matroid. Kruskal's correctness is not a lucky coincidence but a consequence of the graphic matroid structure.
Question 2 Multiple Choice
Consider two set systems on the same ground set E. System A satisfies: any subset of an independent set is independent, and if |A| < |B| for independent sets A and B, there exists an element of B \ A that can be added to A while preserving independence. System B satisfies only the first property. Which is a matroid, and what is the significance of the difference?
ABoth are matroids; the exchange axiom is a consequence of the first property
BSystem A is a matroid; the exchange axiom ensures all maximal independent sets have the same size, which is what makes greedy work
CSystem B is a matroid; the exchange axiom is an optional strengthening that improves efficiency
DNeither is a matroid without also verifying that the empty set is independent
System A satisfies all three matroid axioms (empty set independent, hereditary, exchange). System B satisfies only the hereditary property — it is called an 'independence system' or 'simplicial complex,' but not a matroid. The exchange axiom is the defining property that separates matroids: it ensures all bases (maximal independent sets) have the same size, which is precisely what guarantees the greedy algorithm works. Without the exchange axiom, different greedy choices can lead to differently-sized maximal independent sets with different weights, and greedy may fail.
Question 3 True / False
In a linear matroid, the independent sets are the linearly independent subsets of a collection of vectors. This satisfies the matroid axioms because: any subset of a linearly independent set is linearly independent (hereditary), and if A and B are linearly independent with |A| < |B|, you can always add some vector from B to A and preserve independence (exchange).
TTrue
FFalse
Answer: True
Both properties follow from the theory of vector spaces. The hereditary property holds because linear independence is preserved when you remove vectors. The exchange property follows from the rank theorem: if |A| < |B|, then the span of A has smaller dimension than the span of B, so there must exist a vector in B outside the span of A — adding it to A increases the rank by 1, preserving independence. This confirms that linear matroids are matroids, not just by analogy but by proof.
Question 4 True / False
Because matroids generalize both forests and linear independence, any set system that shares properties with forests is expected to also share properties with linear independence, and vice versa.
TTrue
FFalse
Answer: False
Matroids identify specific axioms (hereditary + exchange) that both forests and linear independence satisfy. But 'sharing properties with forests' is too vague to imply matroid structure — many set systems share some properties with forests without satisfying the exchange axiom. The matroid axioms are precise: a set system that is hereditary but lacks the exchange axiom is not a matroid and the greedy theorem does not apply. The abstraction works only because both forests and linear independence satisfy exactly the same three axioms, not because of a looser resemblance.
Question 5 Short Answer
What does the matroid greedy theorem say, and why does it explain both when greedy works and when it fails?
Think about your answer, then reveal below.
Model answer: The matroid greedy theorem states: the greedy algorithm (always add the highest-weight element that preserves independence) finds a maximum-weight basis if and only if the independence system is a matroid. This is an exact characterization — not just a sufficient condition. It explains when greedy works (Kruskal's algorithm on spanning trees, certain scheduling problems) because those problems have underlying matroid structure. It also explains when greedy fails: problems like shortest path in a graph, knapsack, or set cover do not have matroid structure, so the greedy choice at each step can lead to globally suboptimal solutions. Identifying whether a combinatorial optimization problem has matroid structure is thus the key question for justifying (or rejecting) a greedy approach.
The power of the theorem is its bi-directional nature: matroids are precisely the combinatorial structures on which greedy is optimal. This means failure of greedy is evidence of non-matroid structure, and success of greedy is explained by matroid structure — unifying many seemingly unrelated algorithmic results under a single combinatorial framework.