Minimum spanning trees: cut and cycle properties, uniqueness

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Edges in a tree on n vertices? from Lesson 0.2.3
• Greedy algorithm: what must be proved? from Lesson 4.2.1
• An edge closing a path into a loop forms? from Lesson 0.2.3

1 · The Hook

🎣

Six towns must be linked by cable so that every town can reach every other, using the least total cable. Whatever you choose, it will contain no cycle (a cycle wastes one cable), so it is a tree touching all vertices: a minimum spanning tree (MST). Two simple properties explain every MST algorithm and answer most GATE MST questions.

2 · Predict First

🤔

In the six-town graph, which edge is certainly not in the cheapest network: A–B (4) or B–C (1)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A–B: the cycle A–B–C has edges 4, 1, 2, and its heaviest edge 4 can be dropped without disconnecting anything.

Definitions

• Spanning tree: a tree using all V vertices of a connected graph; it has V − 1 edges.
• MST: a spanning tree with the minimum total weight.
• The complete graph Kₙ has nⁿ⁻² spanning trees (Cayley's formula), so trying them all is hopeless.

Cut property (why an edge is safe)

Split the vertices into two groups (a cut). A minimum-weight edge crossing the cut belongs to some MST; if it is the unique lightest crossing edge, it belongs to every MST.

Cycle property (why an edge is useless)

If an edge is strictly the heaviest on some cycle, it is in no MST.

Consequences GATE uses

• Distinct edge weights ⇒ the MST is unique.
• The lightest edge of the graph (if unique) is in every MST.
• Adding the same constant to every weight, or applying any increasing function, does not change which trees are MSTs (it can change shortest paths).
• An MST does not in general contain shortest paths between vertices.

The six-town MST

B–C 1, A–C 2, D–E 2, E–F 3, B–D 5: total 13, unique. Each other edge is heaviest on a cycle: A–B 4 (A–B–C), C–D 8 (C–B–D), D–F 6 (D–E–F), C–E 10 (C–B–D–E).

4 · Visual

The six-town MST (red, weight 13). Every dashed edge is the heaviest edge on some cycle, so it is in no MST.

5 · Worked Examples

Example 1 Easy

How many edges does an MST of a connected 40-vertex graph have?

Solution

39.

Example 2 Medium

K₄ with all six edges of weight 1: how many MSTs?

Solution

Every spanning tree has weight 3, so all 16 (4⁴⁻²) are MSTs.

Example 3 GATE

Triangle a–b 1, b–c 1, a–c 1.5. Is the shortest path from a to c inside the MST?

Solution

MST = {a–b, b–c} (weight 2); in it a to c costs 2, but the shortest path is the direct edge 1.5. No: MSTs do not preserve shortest paths.

6 · GATE Traps

⚠️

• Unique MST needs distinct weights (sufficient, not necessary); with ties there may be several.
• Cycle property needs strictly heaviest.
• Adding a constant keeps the MST but can change shortest paths.
• Number of spanning trees of Kₙ: nⁿ⁻², not n!.

7 · Memory Hook

🧠

"Cheapest across a cut is in; heaviest on a cycle is out."

8 · Connect the Dots

The cut property says which edges are safe. Kruskal's algorithm, next, uses it by sorting edges and adding each unless it closes a cycle, with a union–find structure to test that fast.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markMST weight

Total weight of the six-town MST?

Numerical answer: ________

Q2NAT1 markEdges

An MST of a connected graph with 50 vertices has how many edges?

Numerical answer: ________

Q3NAT2 marksCounting MSTs

K₅ with every edge of weight 1. How many minimum spanning trees?

Numerical answer: ________

Q4MCQ1 markConstant shift

Every edge weight of a connected graph is increased by 10. Then:

• (A) the MSTs stay the same
• (B) the MSTs may change
• (C) the MST weight is unchanged
• (D) every shortest path stays the same

Q5MSQ2 marksMST facts

Which are true for a connected undirected weighted graph?

• (A) An edge that is strictly the heaviest on some cycle is in no MST.
• (B) An MST always contains a shortest path between every pair of vertices.
• (C) If the lightest edge is unique, it is in every MST.
• (D) If all edge weights are distinct, the MST is unique.

10 · Rule Card

• Spanning tree: V − 1 edges; Kₙ has nⁿ⁻² spanning trees.
• Cut property: lightest crossing edge is safe (unique ⇒ in every MST).
• Cycle property: strictly heaviest on a cycle ⇒ in no MST.
• Distinct weights ⇒ unique MST. Constant shift keeps MSTs, not shortest paths.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

spanning treeminimum spanning treeCayley's formulacut propertycycle propertyMST uniquenessMST vs shortest paths

12 · Answer Vault