Minimum spanning trees

ACompressed recap

🧾

MST: V − 1 edges; Kₙ has nⁿ⁻² spanning trees; cut property (lightest crossing edge safe), cycle property (strictly heaviest on a cycle excluded); distinct weights ⇒ unique MST; constant shift keeps MSTs. Kruskal: sort edges, union–find, O(E log E). Prim: one tree, cheapest edge out, Θ(V²) array or O(E log V) heap.

BMerged rule card

6.2.1 Minimum spanning trees: cut and cycle properties, uniqueness

• 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.

6.2.2 Kruskal's algorithm and union–find

• Kruskal: sort edges; add (u, v) if find(u) ≠ find(v); stop at V − 1 edges.
• O(E log E) = O(E log V); the partial result is a forest.
• Union by rank: height ≤ log n; plus path compression: ~O(α(n)) per operation.

6.2.3 Prim's algorithm; MST complexities

• Prim: grow one tree; add the outside vertex with the smallest key (cheapest edge in).
• Θ(V²) array (dense graphs); O(E log V) binary heap; O(E + V log V) Fibonacci heap.
• Prim one tree; Kruskal a forest; both via the cut property.

CInterleaved GATE-style questions

Q1NAT1 markMST

Number of spanning trees of K₄?

Numerical answer: ________

Q2MCQ1 markCycle property

In the six-town graph, which edge is strictly the heaviest on the cycle C–D–E?

• (A) none
• (B) C–D
• (C) C–E
• (D) D–E

Q3NAT2 marksKruskal

Kruskal on the six-town graph: what is the weight of the fifth (last) edge accepted?

Numerical answer: ________

Q4NAT2 marksMST count

A 4-cycle a–b–c–d–a with every edge of weight 1. How many MSTs?

Numerical answer: ________

Q5MCQ1 markKruskal

Kruskal's algorithm tests whether an edge creates a cycle using:

• (A) a union–find structure
• (B) DFS finish times
• (C) a max-heap
• (D) BFS from scratch every time

Q6NAT2 marksPrim

Prim from C on the six-town graph: weight of the second edge added?

Numerical answer: ________

Q7MCQ1 markPrim cost

For a sparse graph with E = Θ(V), the fastest of these Prim versions is:

• (A) neither works
• (B) both equal
• (C) array, Θ(V²)
• (D) binary heap, O(E log V) = O(V log V)

Q8MSQ2 marksMST facts

Which are true?

• (A) An MST is a shortest-path tree from every vertex.
• (B) Squaring all (positive) edge weights does not change the MSTs.
• (C) A graph with repeated weights may still have a unique MST.
• (D) An MST has V − 1 edges.

DAnswer Vault