Minimum Spanning Trees
Connect all vertices with least total weight.
Key idea
Connect all vertices with least total weight.
In depth
An MST connects all vertices with minimum total weight. Kruskal adds the cheapest edge that does not form a cycle; Prim grows the tree from a start vertex by the cheapest outgoing edge. Both are greedy and correct.
Worked example
Edges AB 1, BC 2, AC 3: MST = AB, BC, with weight 3.
Real-world uses
- Laying fibre-optic or water pipes at the lowest total cost
Common mistake
Allowing cycles in Kruskal’s algorithm.
How to learn this
- Read the key idea and say it in your own words.
- Work through the worked example, then try a similar problem.
- Use the interactive lesson’s visual and mini-quiz to check the pattern.
Frequently asked questions
What is Minimum Spanning Trees?
Connect all vertices with least total weight. It is a topic at the expert level in Discrete Math & Number Theory.
Where is Minimum Spanning Trees used in real life?
Real-world examples: Laying fibre-optic or water pipes at the lowest total cost.
What should I learn before Minimum Spanning Trees?
Make sure you are comfortable with Spanning Trees, the previous topic in Discrete Math & Number Theory.
What is a common mistake with Minimum Spanning Trees?
Allowing cycles in Kruskal’s algorithm.
How can I practise Minimum Spanning Trees?
Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.
What comes after Minimum Spanning Trees?
Move on to Shortest Paths (Dijkstra) next.
Related expert topics in Discrete Math & Number Theory
- Strong Induction – Assume all earlier cases to prove the next.
- Well-Ordering Principle – Every nonempty set of positive integers has a least element.
- Partial Orders – Reflexive, antisymmetric, transitive relations.
- Cardinality of Sets – Comparing sizes of infinite sets.
- Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
- Cantor’s Diagonal Argument – Proof that real numbers are uncountable.