Skip to main content

MST, Cut Property, and Cycle Property

What This Concept Is​

An MST minimizes total selected edge weight while connecting all vertices of a connected undirected graph without cycles. A disconnected graph has a minimum spanning forest, one tree per component. Negative weights are allowed.

Cut rule with ties: a lightest edge across a cut belongs to some MST. A uniquely lightest crossing edge belongs to every MST. Cycle rule: a heaviest edge on a cycle can be omitted by some MST; if uniquely heaviest, it is in no MST.

Why It Matters Here​

The words "some", "every" and "unique" determine whether an implementation may safely choose one tied edge or permanently rule it out. Greedy extension also needs a cut respecting the forest already chosen, not an unrelated claim that each edge individually belongs to some optimum.

Concrete Examples​

In an all-weight-1 triangle, every two-edge tree is an MST. Each edge is heaviest on the cycle, yet every edge belongs to some MST. Thus "a maximum cycle edge is in no MST" is false without strictness.

Exchange proof: let A be a forest contained in an MST T, and choose a cut with no A edge crossing it. Add a light crossing edge e absent from T. Its endpoints define a cycle in T+e, which contains another crossing edge f. Since the cut respects A, f is not in A. Replace f by e; weight cannot increase, so an MST containing A+e exists. A tie proves existence, not contradiction or uniqueness.

Common Confusion / Misconceptions​

A shortest-path tree minimizes individual source distances, not total connecting weight. An MST path need not minimize additive distance. Distinct weights are sufficient, not necessary, for uniqueness. Any MST can be produced by Kruskal under a suitable ordering of tied edges; a fixed tie order merely selects one.

How To Use It​

Accept equal-weight alternative witnesses. Verify a forest has V-c edges and the same connected components as the input. For optimality, a useful certificate is that every non-tree edge is at least as heavy as the maximum edge on its forest path, for endpoints in the same component. Derive the exchange reasoning instead of labeling a finite test "proof in code".

Check Yourself​

  1. What does a uniquely light cut edge guarantee?
  2. Why is a respecting cut needed when extending a chosen forest?
  3. What changes in the cycle rule when weights tie?
  4. Why is distinctness unnecessary for existence?

Mini Drill or Application​

List all MSTs of the equal triangle and certify one using cuts and exchange. Construct a triangle where the MST route from 0 to 2 is longer than a direct edge. Explain which objective each result optimizes. See P13.

Read This Only If Stuck​

Find MST exchange proofs and tied cut/cycle properties in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.