Graph Theory37 sections · 1633 units
Open in Course

Edge Classification

Three categories

Build one MST using Kruskal. Now classify:

"none": Edge weight is strictly greater than the maximum edge weight on the MST path between its endpoints. Never picked.

"any": Edge is a bridge in the MST subgraph formed by all edges of its weight. Always needed.

"at least one": Edge is in the MST but not a bridge. Can be swapped with another edge of the same weight.

This classification tells you which edges are always in the MST, which are sometimes in, and which are never in.