Self-checkedTier 1 13 min readalgo.mst-basics

Spanning trees and the cut property

Spanning trees and minimum spanning trees: definition, V - 1 edges, how many spanning trees a graph has (Cayley's n^(n-2)), the cut property and the cycle property that make greedy choices safe, the generic MST algorithm, uniqueness when weights are distinct, invariance of the MST under order-preserving changes of weights, the bottleneck property, and the difference from shortest-path trees.

Why it exists

Connect $n$ towns by roads, computers by cables, or pins on a circuit board, using as little material as possible: this is the minimum spanning tree (MST) problem. It is the standard example of a problem where the greedy method works, and its proof is a clean application of the cut property. GATE asks for the number of edges, the weight of an MST for a given graph, which edges must or cannot be in it, how it changes when weights change, and the running time of the two classic algorithms (next page).

Prerequisites

Greedy method and exchange argument BFS and DFS

You need the greedy method (greedy method) and graph traversal (BFS and DFS).

Precise definitions

Spanning tree. A subgraph of a connected undirected graph $G = (V, E)$ that contains all the vertices, is connected and has no cycle (so it is a tree). It has exactly $V - 1$ edges. Equivalent descriptions: a minimal connected spanning subgraph (removing any edge disconnects it), a maximal acyclic one (adding any edge creates a cycle).

Weight. Each edge $e$ has a weight $w(e)$ ; the weight of a tree is the sum of the weights of its edges.

Minimum spanning tree. A spanning tree of the smallest possible weight. There can be several if weights tie.

Cut. A partition of the vertices into two non-empty sets $(S, V \setminus S)$ . An edge crosses the cut if its ends are on different sides. A cut respects a set $A$ of edges if no edge of $A$ crosses it. A light edge crossing a cut is a crossing edge of minimum weight.

Safe edge. For a set $A$ of edges contained in some MST, an edge $e$ is safe for $A$ if $A \cup \{e\}$ is still contained in some MST.

How it works

Counting and listing spanning trees

A graph can have a great many spanning trees: $K_n$ , the complete graph on $n$ vertices, has $n^{n-2}$ of them (Cayley's formula): $1, 3, 16, 125, 1296$ for $n = 2, \ldots, 6$ (checked by listing them all). A tree has exactly one; a cycle of $n$ vertices has $n$ (leave out one edge).

The program lists every spanning tree of a small weighted graph by trying all subsets of edges of the right size and keeping the acyclic ones. The graph has five vertices $A$ to $E$ and the edges $AB = 4$ , $AC = 1$ , $BC = 3$ , $BD = 6$ , $CD = 5$ , $CE = 7$ , $DE = 2$ .

#include <stdio.h>
 
struct edge { int u, v, w; };
 
static int find(int p[], int x) { return p[x] == x ? x : find(p, p[x]); }
 
int main(void) {
    const char *name = "ABCDE";
    struct edge e[7] = {{0, 1, 4}, {0, 2, 1}, {1, 2, 3}, {1, 3, 6}, {2, 3, 5}, {2, 4, 7}, {3, 4, 2}};
    int count = 0, best = 1 << 20;
    for (int mask = 0; mask < 128; mask++) {
        int bits = 0, w = 0, p[5] = {0, 1, 2, 3, 4}, acyclic = 1;
        for (int i = 0; i < 7; i++) {
            if (!(mask >> i & 1)) continue;
            bits++;
            w += e[i].w;
            int a = find(p, e[i].u), b = find(p, e[i].v);
            if (a == b) acyclic = 0; else p[a] = b;
        }
        if (bits != 4 || !acyclic) continue;               /* 4 edges and no cycle = a spanning tree of 5 vertices */
        count++;
        if (w < best) best = w;
        printf("tree");
        for (int i = 0; i < 7; i++) if (mask >> i & 1) printf(" %c%c", name[e[i].u], name[e[i].v]);
        printf("  weight %d\n", w);
    }
    printf("%d spanning trees, the lightest has weight %d\n", count, best);
    return 0;
}

tree AB AC BD CE  weight 18
tree AB BC BD CE  weight 20
tree AC BC BD CE  weight 17
tree AB AC CD CE  weight 17
tree AB BC CD CE  weight 19
tree AC BC CD CE  weight 16
tree AB BD CD CE  weight 22
tree AC BD CD CE  weight 19
tree AB AC BD DE  weight 13
tree AB BC BD DE  weight 15
tree AC BC BD DE  weight 12
tree AB AC CD DE  weight 12
tree AB BC CD DE  weight 14
tree AC BC CD DE  weight 11
tree AB BD CD DE  weight 17
tree AC BD CD DE  weight 14
tree AB AC CE DE  weight 14
tree AB BC CE DE  weight 16
tree AC BC CE DE  weight 13
tree AB BD CE DE  weight 19
tree AC BD CE DE  weight 16
21 spanning trees, the lightest has weight 11

All 21 spanning trees of a weighted graph, lightest first: start

Computed by a script, not typed

tree	edges	weight
tree 1
tree 2
tree 3
tree 4
tree 5
tree 6
tree 7
tree 8
tree 9
tree 10
tree 11
tree 12
tree 13
tree 14
tree 15
tree 16
tree 17
tree 18
tree 19
tree 20
tree 21

Step 0

The graph has 5 vertices A to E and 7 edges AB 4, AC 1, BC 3, BD 6, CD 5, CE 7, DE 2. A program tried all 128 sets of edges and kept those with 4 edges and no cycle: each is a spanning tree.

0 / 21

computed by script: the quantities are measured by running C, or evaluated, one row at a time. python3 scripts/gen-algo-graph-traces.py

There are $21$ spanning trees, of weights between $11$ and $22$ ; the minimum, $AC + BC + CD + DE = 1 + 3 + 5 + 2 = 11$ , is unique here. No clever algorithm tries them all (the number grows exponentially); the greedy algorithms of the next page find the minimum directly, and the reason they are correct is the cut property.

The cut property

Cut property. Let $A$ be a set of edges contained in some MST, let $(S, V \setminus S)$ be a cut that respects $A$ , and let $e$ be a light edge crossing the cut. Then $e$ is safe for $A$ .

Proof (exchange). Let $T$ be an MST containing $A$ . If $e \in T$ we are done. Otherwise adding $e$ to $T$ creates a cycle, which must cross the cut a second time through another edge $f \in T$ (a cycle crosses a cut an even number of times). Since $A$ respects the cut, $f \notin A$ . Replace $f$ by $e$ : $T' = T - f + e$ is a spanning tree with weight $w(T) - w(f) + w(e) \le w(T)$ , because $e$ is light and $f$ crosses the same cut. So $T'$ is also an MST, contains $A \cup \{e\}$ , and $e$ is safe. $\blacksquare$

Consequence. The lightest edge incident to any vertex belongs to some MST (take the cut $(\{v\}, V \setminus \{v\})$ ). If all weights are distinct, the light edge of every cut is in every MST.

Cycle property. If an edge is the unique heaviest edge on some cycle, then it belongs to no MST (remove it from a tree that contains it and reconnect the two halves with another edge of the cycle: the weight drops). With ties, a heaviest edge of a cycle may be in some MST but never has to be.

The generic algorithm

Start with $A = \emptyset$ . While $A$ is not a spanning tree: find a cut that respects $A$ , take a light edge crossing it, and add it to $A$ . After $V - 1$ additions $A$ is an MST (each step keeps $A$ inside some MST, by the cut property). Kruskal's algorithm and Prim's algorithm are two ways of choosing the cut: Kruskal takes the lightest edge joining two different trees of the current forest, Prim always takes the lightest edge leaving the single tree grown so far.

Facts that GATE uses

Number of edges of every spanning tree: $V - 1$ . A spanning tree exists if and only if the graph is connected; otherwise one gets a spanning forest.
Distinct weights $\Rightarrow$ a unique MST. With ties there may be several, but all MSTs have the same sorted list of edge weights (and the same total).
Order-preserving changes do not change the MST. Adding a constant to every weight, multiplying by a positive constant, squaring positive weights: the sorted order of the edges stays the same, and Kruskal looks only at that order, so the MSTs are the same. (Shortest paths, by contrast, change, because a path adds up weights of several edges.) Checked on 150 random graphs.
Bottleneck property. An MST also minimises the largest edge weight among all spanning trees (a "minimum bottleneck" tree), and for any two vertices the path between them in an MST has the smallest possible maximum edge.
Maximum spanning tree: negate the weights (or run Kruskal in decreasing order).
MST is not a shortest-path tree. The MST minimises the total weight of the tree; a shortest-path tree from a source minimises the weight of each path from the source. They can be different trees on the same graph (Dijkstra).

Worked examples

EX 1Edges of a spanning tree

Easy

A connected graph has $10$ vertices. Every spanning tree has $9$ edges. If the graph has $30$ edges, then $21$ edges are left out of any spanning tree. A spanning tree of a graph with $n$ vertices and $m$ edges leaves out $m - (n - 1)$ edges; this number, $m - n + 1$ , is the number of independent cycles.

EX 2Count spanning trees of small graphs

Easy

A cycle of $4$ vertices: remove one of the $4$ edges: $4$ spanning trees. The complete graph $K_4$ : $4^{2} = 16$ . A triangle with one extra pendant vertex attached to one corner: $3$ (the pendant edge is in every spanning tree; choose which edge of the triangle to leave out). The graph of the page: $21$ (listed by the program).

EX 3Apply the cut property

Medium

Page graph. Cut $(\{A, B, C\}, \{D, E\})$ : the crossing edges are $BD = 6$ , $CD = 5$ , $CE = 7$ ; the light edge is $CD = 5$ . So $CD$ is in some MST; since all weights are distinct it is in every MST (and indeed in the unique one of weight $11$ ). Cut $(\{A\}, \text{rest})$ : edges $AB = 4$ , $AC = 1$ : the light edge $AC$ is in the MST. Cut $(\{E\}, \text{rest})$ : $CE = 7$ , $DE = 2$ : $DE$ is in the MST, while $CE$ need not be (and is not).

EX 4Cycle property

Medium

In the triangle $A, B, C$ of the page graph the edges are $AB = 4$ , $AC = 1$ , $BC = 3$ : the heaviest is $AB = 4$ and it is unique, so $AB$ is in no MST (the table agrees: the minimum tree $AC, BC, CD, DE$ does not use it). In the cycle $B, C, D$ the edges $BC = 3$ , $CD = 5$ , $BD = 6$ : $BD$ is the unique heaviest, so it is in no MST either.

EX 5Typical statements

GATE level

(a) If all edge weights are distinct the MST is unique: true. (b) If every edge weight is squared, the MST changes: false (for positive weights the order is the same), but the weight of the MST changes. (c) The edge of smallest weight in the graph is always in some MST: true (cut around either end, or the cut property); if it is the unique smallest, in every MST. (d) The edge of largest weight is never in an MST: false: a bridge (an edge whose removal disconnects the graph) must be in every spanning tree, however heavy. (e) A graph with $V$ vertices and $E = V - 1$ edges has how many spanning trees if connected? Exactly one (it is a tree). (f) Every edge of a spanning tree is on a cut for which it is a light edge: true for an MST (remove the edge to split the tree into two parts).

Cheat box

Spanning tree: all $V$ vertices, connected, acyclic, exactly $V - 1$ edges; exists iff the graph is connected. $K_n$ has $n^{n-2}$ .
Cut property: the lightest edge across a cut that respects $A$ is safe. Cycle property: the unique heaviest edge of a cycle is in no MST.
Distinct weights $\Rightarrow$ unique MST; all MSTs have the same multiset of edge weights.
Add a constant, scale, square (positive weights): MST unchanged (only the order matters).
MST minimises total weight and also the largest edge. A bridge is in every spanning tree. Not the same as a shortest-path tree.
Generic algorithm: add safe (light) edges one at a time, $V - 1$ times.

Traps and GATE patterns

Connections

Builds on

Greedy method and exchange argument BFS and DFS

Unlocks

Greedy method and exchange argumentimplemented by BFS and DFSimplemented by Kruskal and PrimPrerequisite of Kruskal and Primuses

Across subjects

No cross-subject links yet.

Within this subject

Greedy method and exchange argumentuses BFS and DFSuses Kruskal and Primimplemented-by Dijkstra's algorithmcontrasts-with

The greedy proof technique is the exchange argument of the greedy method; trees are found inside a graph by searches. The two algorithms that apply the cut property are in Kruskal and Prim; Dijkstra's algorithm grows a tree too, but a shortest-path tree.

PYQs

21 previous year questions from your book. I re-solved each one myself (13 by running or simulating, 8 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · Set 1 · MSQQ2 · page 113 of the book

Let G(V,E) be a simple, undirected, edge-weighted
graph with unique edge weights. Which of the
following statements about the minimum spanning
trees (MST) of G is/are true?

(a)In every cycle C of G, the edge with the largest weight in C is not in any MST
(b)In every cycle C of G, the edge with the smallest weight in C is in every MST
(c)For every vertex v ∈V, the edge with the largest weight incident on v is not in any MST
(d)For every vertex v ∈V, the edge with the smallest weight incident on v is in every MST

GATE 2025 · Set 1 · MCQ · 1 markQ4 · page 113 of the book

Let G be any undirected graph with positive edge
weights, and T be a minimum spanning tree of G.
For any two vertices, u and v, let d1(u,v) and d2(u,v)
be the shortest distances between u and v in G and
T, respectively. Which ONE of the options is
CORRECT for all possible G, T, u and v?

(a)d1 (u, v) = d2 (u, v)
(b)d1 (u, v) ≤ d2 (u, v)
(c)d1 (u, v) ≥ d2 (u, v)
(d)d1 (u, v) != d2 (u, v)

GATE 2025 · Set 2 · MCQQ5 · page 113 of the book

Let G be an edge-weighted undirected graph with
positive edge weights. Suppose a positive constant α
is added to the weight of every edge. Which ONE of
the following statements is TRUE about the
minimum spanning trees (MSTs) and shortest paths
(SPs) in G before and after the edge weight update?

(a)Every MST remains an MST, and every SP remains an SP.
(b)MSTs need not remain MSTs, and every SP remains an SP.
(c)Every MST remains an MST, and SPs need not remain SPs.
(d)MSTs need not remain MSTs, and SPs need not remain SPs. ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2025 · Set 1 · NAT · 2 marksQ6 · page 114 of the book

The maximum value of x such that the edge
between the nodes B and C is included in every
minimum spanning tree of the given graph is

. (Answer in integer)

year not read yetQ8 · page 114 of the book

The number of spanning tree in complete labelled
graph of 4 vertices labelled A, B, C, and D is......

GATE 2024 · Set 2 · MCQ · 2 marksQ9 · page 114 of the book

Let G be an undirected connected graph in which
every edge has a positive integer weight. Suppose
that every spanning tree in G has even weight.
Which of the following statements is/are TRUE
for every such graph G?

(a)All edges in G have even weight.
(b)In each cycle C in G, all edges in C have even weight.
(c)All edges in G have even weight or all edges in G have odd weight.
(d)In each cycle C in G, either all edges in C have even weight OR all edges in C have odd weight.

GATE 2024 · Set 2 · NATQ10 · page 114 of the book

The number of distinct minimum-weight spanning
trees of the following graph is
.

GATE 2022 · MSQQ12 · page 114 of the book

Consider a simple undirected weighted graph G,
all of whose edge weights are distinct.
Which of the following statements about the
minimum spanning trees of G is/are TRUE?

(a)The edge with the second smallest weight is always part of any minimum spanning tree of G.
(b)One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G
(c)Suppose S⊆V be such that S != φ and S != V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V∖S. Such an edge will always be part of any minimum spanning tree of G
(d)G can have multiple minimum spanning trees. ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2021 · Set 1 · NAT · 1 markQ13 · page 115 of the book

Consider the following undirected graph with
edge weights as shown:

The number of minimum-spanning trees of the
graph is
.

GATE 2021 · Set 2 · MCQ · 2 marksQ15 · page 115 of the book

Let G be a connected undirected weighted graph.
Consider the following two statements.
S1 : There exists a minimum weight edge in G
which is present in every minimum spanning
tree of G.
S2 : If every edge in G has distinct weight, then
G has a unique minimum spanning tree.
Which one of the following options is correct?

(a)S 1 is true and S 2 is false.
(b)S 1 is false and S 2 is true.
(c)Both S 1 and S 2 are true.
(d)Both S 1 and S 2 are false.

GATE 2020 · MCQ · 2 marksQ17 · page 115 of the book

Let G = (V, E) be a weighted undirected graph and
let T be a Minimum Spanning Tree (MST) of G
maintained using adjacency lists. Suppose a new
weighted edge (u,v) ∈ V × V is added to G. The
worst case time complexity determining if T is still
an MST of the resultant graph is

(a)θ(|E| log |V|)
(b)θ(|E| + |V|)
(c)θ(|E| |V|)
(d)θ (|V|)

GATE 2019 · MCQ · 2 marksQ19 · page 116 of the book

Let G be any connected, weighted, undirected
graph.
I. G has a unique minimum spanning tree, if no
two edges of G have the same weight.
II. G has a unique minimum spanning tree, if, for
every cut of G, there is a unique minimum-
weight edge crossing the cut.
Which of the above two statements is/are
TRUE?

(a)I only
(b)II only
(c)Both I and II
(d)Neither I nor II

GATE 2018 · NAT · 2 marksQ20 · page 116 of the book

Consider the following undirected graph G:

Choose a value of x that will maximize the
number of minimum weight spanning trees
(MWSTs) of G. The number of MWSTs of G for
this value of x is
.

GATE 2016 · Set 1 · MCQ · 2 marksQ21 · page 116 of the book

Let G be a complete undirected graph on 4
vertices having 6 edges with weights being 1,2
a minimum weight spanning tree of G can have
is
.

(a)4
(b)5
(c)6
(d)7 W= [ 0 2 8 5 2 0 5 8 8 5 0 x 5 8 x 0 ] The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is . ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2016 · Set 1 · MCQQ22 · page 116 of the book

Let G be a weighted connected undirected graph
with distinct positive edge weights. If every edge
weight is increased by the same value, then which
of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does
not change

(a)P only
(b)Q only
(c)Neither P nor Q
(d)Both P and Q

GATE 2016 · Set 1 · MCQQ23 · page 116 of the book

G = (V, E) is an undirected simple graph in which
each edge has a distinct weight, and e is a particular
edge of G. Which of the following statements about
the minimum spanning trees (MSTs) of G is/are
TRUE?
I. If e is the lightest edge of some cycle in G, then
every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then
every MST of G excludes e

(a)i only
(b)ii only
(c)both i and ii
(d)neither i and ii

GATE 2015 · Set 3 · NAT · 2 marksQ27 · page 117 of the book

Let G be a connected undirected graph of 100
vertices and 300 edges. The weight of a minimum
spanning tree of G is 500. When the weight of
each edge of G is increased by five, the weight of
a minimum spanning tree becomes
.

GATE 2012 · MCQ · 2 marksQ29 · page 117 of the book

Let G be a weighted graph with edge weights
greater than one and G' be the graph constructed by
squaring the weights of edges in G. Let T and T' be
the minimum spanning trees of G and G' ,
respectively, with total weights t and t' . Which of
the following statements is TRUE?

(a)T' = T with total weight t' = t 2
(b)T' = T with total weight t' < t 2
(c)T' ≠ T but total weight t' = t2
(d)None of the above

GATE 2007 · MCQQ39 · page 119 of the book

Let w be the minimum weight among all edge
weights in an undirected connected graph. Let e be a
specific edge of weight w. Which of the following is
False ?

(a)There is a minimum spanning tree containing e.
(b)If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
(c)Every minimum spanning tree has an edge of weight w.
(d)e is present in every minimum spanning tree.

GATE 2005 · MCQ · 1 markQ44 · page 120 of the book

Let s and t be two vertices in a undirected graph
G=(V, E) having distinct positive edge weights.
Let [X, Y] be a partition of V such that s∈ X and
t∈⁡Y. Consider the edge e having the minimum
weight amongst all those edges that have one
vertex in X and one vertex in Y.
The edge e must definitely belong to:

(a)the minimum weighted spanning tree of G
(b)the weighted shortest path from s to t
(c)each path from s to t
(d)the weighted longest path from s to t

GATE 2005 · MCQ · 1 markQ45 · page 120 of the book

An undirected graph G has n nodes. Its adjacency
matrix is given by an nxn square matrix whose
(i) diagonal elements are 0's and
(ii) non-diagonal elements are 1's.
which one of the following is TRUE?

(a)Graph G has no minimum spanning tree (MST)
(b)Graph G has a unique MST of cost n-1
(c)Graph G has multiple distinct MSTs, each of cost n-1
(d)Graph G has multiple spanning trees of different costs

Self-check

Question 1

How many edges does a spanning tree of a connected graph with $12$ vertices have?

Show answer

$11$ .

Question 2

How many spanning trees does the complete graph $K_5$ have?

Show answer

$5^3 = 125$ .

Question 3

If every edge weight of a connected graph is replaced by its cube (positive weights), does the MST change?

Show answer

No: the order of the weights is unchanged, so the same edges form an MST; only its total weight changes.

Question 4

State the cut property in one sentence.

Show answer

For a cut that no chosen edge crosses, the lightest edge crossing it can be added to the chosen edges and they still lie in some minimum spanning tree.

Revision card

One-screen revision

Spanning tree: $V - 1$ edges, connected, acyclic; $K_n$ has $n^{n-2}$ .
Cut property (light edge across a cut respecting $A$ is safe) $\Rightarrow$ greedy MST is correct. Cycle property: unique heaviest edge is excluded.
Distinct weights $\Rightarrow$ unique MST; monotone weight changes keep it; a bridge is always in.
MST $\ne$ shortest-path tree.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd edition), Chapter 23 Minimum Spanning Trees (23.1 growing a minimum spanning tree)
·Kleinberg and Tardos, Algorithm Design, Section 4.5 The Minimum Spanning Tree Problem (the cut and cycle properties)
·Dasgupta, Papadimitriou, Vazirani, Algorithms, Section 5.1 Minimum spanning trees

Verification

On 300 random weighted graphs of up to 6 vertices EVERY spanning tree was enumerated and the minimum weight compared with Kruskal and Prim; with distinct weights the minimum tree was unique; the cut property (the lightest edge across a cut belongs to some minimum spanning tree, and to every one when weights are distinct, tested on every cut) and the cycle property (the unique heaviest edge of a cycle is in no minimum spanning tree, tested on every cycle) held. The number of spanning trees of K_n was counted as n^(n-2) for n up to 6 and the page graph has 21 spanning trees with the unique minimum 11 (the C program on this page lists them all). On 150 random graphs the minimum spanning tree was the same after adding a constant to every weight, squaring them, or applying 3w + 7, and its largest edge equalled the best possible largest edge over all spanning trees. The textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (loop counts, recurrences, merge and quicksort counts and averages, hash probes and load-factor formulas, DP tables, MST and shortest-path runs, Floyd matrices); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

DFS edge types, topological sort and SCC

Kruskal and Prim