Graph Theory37 sections · 1633 units
Open in CourseQuiz: MST Edge in ALL
Knowledge check
Check Your Understanding
Edges in MST: Determine if an edge appears in ALL possible MSTs. Edge appears in all MSTs if:
- A.Both endpoints have degree
- B.Removing it disconnects the graph, or all alternative paths have strictly heavier bottleneck
- C.It's the minimum weight edge in the graph
- D.It's part of the shortest path tree