CSCI2100 · Theorem · Chapter 14 · Graph algorithms
Safe-edge lemma
2 steps of prerequisites below it
If an edge set X lies in some minimum spanning tree and a cut is crossed by no edge of X, then X together with a lightest crossing edge lies in some minimum spanning tree.
Taught in
- 14.2 Weighted graph frontiers: Dijkstra and Prim · introduced
Uses
- Minimum spanning forest · used in its proof, proof step 14.2
Used by
Counterexamples
Everything this builds on, earliest first · 2 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Spanning forest · 14.1
- Minimum spanning forest · 14.1
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.