Minimum Spanning Tree (MST) -- Complete Guide

Minimum Spanning Trees are fundamental in network design, clustering, and approximation algorithms. This guide covers both Kruskal's and Prim's algorithms in depth, along with advanced topics like second-best MST and Boruvka's algorithm.

What is a Spanning Tree?

A spanning tree of a connected, undirected graph G = (V, E) is a subgraph T that:

Is a tree (connected and acyclic)
Contains all V vertices of G
Has exactly V - 1 edges

Key insight: A tree with V vertices always has exactly V-1 edges. Removing any edge disconnects it; adding any edge creates exactly one cycle.

What is a Minimum Spanning Tree?

The spanning tree with the minimum total edge weight.

Fundamental MST Properties

1. Cut Property

Theorem: For any cut (S, V-S) of the graph, the minimum-weight edge crossing the cut must be in every MST (assuming unique edge weights).

Proof intuition: If the MST used a heavier crossing edge instead, we could swap it for the lighter one and get a lighter tree.

2. Cycle Property

Theorem: For any cycle in the graph, the maximum-weight edge in the cycle cannot be in any MST (assuming unique edge weights).

Cycle: A-B-D-C-A, weights: 3, 2, 4, 5. Only the single heaviest edge is guaranteed not to be in MST. MST = {(B,D,2), (A,B,3), (C,D,4)}, weight = 9. The heaviest cycle edge (A,C,5) is indeed excluded.

3. Uniqueness

If all edge weights are distinct, the MST is unique.
If some weights are equal, multiple MSTs may exist (all with the same total weight).

4. Number of Edges

An MST of a connected graph with V vertices always has exactly V - 1 edges.

Algorithm 1: Kruskal's Algorithm

The Idea

Sort all edges by weight (ascending)
Greedily add each edge if it doesn't create a cycle
Use Disjoint Set Union (DSU) for cycle detection
Stop when V-1 edges are added

Why it works: By the cut property, the lightest edge crossing any cut must be in the MST. Kruskal's considers edges lightest-first and adds them if they connect two different components (which is exactly a cut!).

Detailed Visual Walkthrough

Edges sorted by weight: (C,D,1), (B,D,2), (A,B,4), (D,F,6), (B,E,7), (A,C,8), (E,F,9)

V = 6, need V-1 = 5 edges. DSU initial: {A}, {B}, {C}, {D}, {E}, {F}

Skipped edges: (A,C,8) would create cycle A-B-D-C-A; (E,F,9) would create cycle B-E-F-D-B.

DSU (Union-Find) Refresher

CPP

struct DSU {
    vector<int> parent, rank_;

    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false; // already in same component
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        return true;
    }
};

Kruskal's Implementation

CPP

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

struct DSU {
    vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        return true;
    }
};

// Returns {MST weight, MST edges}. If not connected, MST edges < V-1.
pair<long long, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);

    long long mstWeight = 0;
    vector<Edge> mstEdges;

    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mstWeight += e.w;
            mstEdges.push_back(e);
            if ((int)mstEdges.size() == n - 1) break; // MST complete
        }
    }
    return {mstWeight, mstEdges};
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;

    auto [weight, mstEdges] = kruskal(n, edges);

    if ((int)mstEdges.size() < n - 1) {
        cout << "Graph is not connected, no MST exists\n";
    } else {
        cout << "MST weight: " << weight << "\n";
        for (auto& e : mstEdges)
            cout << e.u << " -- " << e.v << " (w=" << e.w << ")\n";
    }
}

Complexity Analysis

Algorithm 2: Prim's Algorithm

The Idea

Start from any vertex, add it to the MST
Maintain a "frontier" of edges connecting MST vertices to non-MST vertices
Greedily pick the cheapest frontier edge
Add the new vertex to the MST, update the frontier
Repeat until all vertices are in the MST

Why it works: Each step adds the lightest edge crossing the cut (MST, non-MST). By the cut property, this edge must be in the MST.

Detailed Visual Walkthrough

Start from vertex A:

MST edges: (A,B,4), (B,D,2), (D,C,1), (D,F,6), (B,E,7). MST weight = 4 + 2 + 1 + 6 + 7 = 20 (same as Kruskal!)

Implementation (Priority Queue)

CPP

#include <bits/stdc++.h>
using namespace std;

// Returns MST weight. Returns -1 if graph is not connected.
long long prim(int n, vector<vector<pair<int,int>>>& adj) {
    vector<bool> inMST(n, false);
    // Min-heap: {edge_weight, vertex}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    pq.push({0, 0}); // start from vertex 0 with "virtual" edge of weight 0
    long long mstWeight = 0;
    int edgesAdded = 0;

    while (!pq.empty() && edgesAdded < n) {
        auto [w, u] = pq.top(); pq.pop();

        if (inMST[u]) continue; // skip if already in MST

        // Add u to MST
        inMST[u] = true;
        mstWeight += w;
        edgesAdded++;

        // Add all edges from u to non-MST vertices
        for (auto [v, weight] : adj[u]) {
            if (!inMST[v]) {
                pq.push({weight, v});
            }
        }
    }

    return (edgesAdded == n) ? mstWeight : -1; // -1 if not connected
}

Implementation with Edge Tracking

CPP

pair<long long, vector<pair<int,int>>> primWithEdges(int n, vector<vector<pair<int,int>>>& adj) {
    vector<bool> inMST(n, false);
    // {weight, vertex, parent}
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;

    pq.push({0, 0, -1});
    long long mstWeight = 0;
    vector<pair<int,int>> mstEdges;

    while (!pq.empty()) {
        auto [w, u, par] = pq.top(); pq.pop();
        if (inMST[u]) continue;

        inMST[u] = true;
        mstWeight += w;
        if (par != -1) mstEdges.push_back({par, u});

        for (auto [v, weight] : adj[u]) {
            if (!inMST[v]) {
                pq.push({weight, v, u});
            }
        }
    }
    return {mstWeight, mstEdges};
}

Dense Graph Prim (O(V^2), no heap)

When the graph is dense (E close to V^2), avoid the priority queue overhead:

CPP

long long primDense(int n, vector<vector<int>>& weight) {
    // weight[i][j] = edge weight, or INF if no edge
    const int INF = 1e9;
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INF); // minimum edge weight to connect to MST
    minEdge[0] = 0;

    long long mstWeight = 0;

    for (int iter = 0; iter < n; iter++) {
        // Find the non-MST vertex with smallest minEdge
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        }

        if (minEdge[u] == INF) return -1; // not connected

        inMST[u] = true;
        mstWeight += minEdge[u];

        // Update minEdge for non-MST neighbors
        for (int v = 0; v < n; v++) {
            if (!inMST[v] && weight[u][v] < minEdge[v]) {
                minEdge[v] = weight[u][v];
            }
        }
    }
    return mstWeight;
}

Complexity Analysis

Note: For the PQ version, E entries can be pushed to the heap (each edge processed once from each direction = O(E) pushes). Each push/pop is O(log(E)) = O(log V). Total: O(E log V).

Kruskal vs Prim -- Comparison

Rule of thumb:

Edge list input -> Kruskal
Adjacency list input, sparse -> Prim (PQ) or Kruskal
Adjacency matrix input, dense -> Prim (array)
Need MST edges explicitly -> Kruskal is simpler

Boruvka's Algorithm

The Idea

Process all components in parallel:

For each component, find the cheapest edge leaving it
Add all such edges (carefully handling duplicates)
Repeat until one component remains

Each round at least halves the number of components, so at most O(log V) rounds.

Round 1:
  Component {A}: cheapest outgoing = (A,B,2)
  Component {B}: cheapest outgoing = (A,B,2)  (same edge!)
  Component {C}: cheapest outgoing = (C,D,1)
  Component {D}: cheapest outgoing = (C,D,1)  (same edge!)
  Component {E}: cheapest outgoing = (B,E,5)
  Component {F}: cheapest outgoing = (D,F,6)

  Add edges: (A,B,2), (C,D,1), (B,E,5), (D,F,6)
  Components after: {A,B,E}, {C,D,F}

Round 2:
  Component {A,B,E}: cheapest outgoing = (B,D,3)
  Component {C,D,F}: cheapest outgoing = (B,D,3)

  Add edge: (B,D,3)
  Components after: {A,B,C,D,E,F}

Done! MST = {(C,D,1), (A,B,2), (B,D,3), (B,E,5), (D,F,6)}
Weight = 1+2+3+5+6 = 17

Implementation

CPP

long long boruvka(int n, vector<Edge>& edges) {
    DSU dsu(n);
    long long mstWeight = 0;
    int numComponents = n;

    while (numComponents > 1) {
        // cheapest[comp] = {weight, edge_index}
        vector<int> cheapest(n, -1);

        for (int i = 0; i < (int)edges.size(); i++) {
            int cu = dsu.find(edges[i].u);
            int cv = dsu.find(edges[i].v);
            if (cu == cv) continue; // same component

            if (cheapest[cu] == -1 || edges[i].w < edges[cheapest[cu]].w)
                cheapest[cu] = i;
            if (cheapest[cv] == -1 || edges[i].w < edges[cheapest[cv]].w)
                cheapest[cv] = i;
        }

        bool merged = false;
        for (int i = 0; i < n; i++) {
            if (cheapest[i] != -1) {
                int ei = cheapest[i];
                if (dsu.unite(edges[ei].u, edges[ei].v)) {
                    mstWeight += edges[ei].w;
                    numComponents--;
                    merged = true;
                }
            }
        }

        if (!merged) break; // graph is disconnected
    }
    return mstWeight;
}

Complexity

Rounds: O(log V) (components at least halve each round)
Per round: O(E) to scan all edges
Total: O(E log V)
Useful in parallel/distributed computing (each component processes independently)

MST Properties and Theorems

Minimum Bottleneck Spanning Tree

The MST is also a minimum bottleneck spanning tree: the path between any two vertices in the MST minimizes the maximum edge weight.

Why? Consider path u -> v in the MST.
If there's a path P with smaller max-edge, then the heaviest edge
on the MST path creates a cycle with P. By the cycle property,
the heaviest edge shouldn't be in the MST -- contradiction.

Adding an Edge to the MST

If you add a non-MST edge (u, v, w) to the MST, it creates exactly one cycle. The MST can be "fixed" by removing the heaviest edge in that cycle.

This means the original wasn't an MST -- contradiction. So in a true MST, adding any non-MST edge and removing the heaviest in the cycle gives a tree with weight >= MST weight.

MST and Cuts

Number of MSTs: Can be computed by considering groups of equal-weight edges. For each weight value, the structure of which components get merged is the same across all MSTs (Kruskal's "same or nothing" property for equal-weight edges).

Second Best MST

Problem

Find the spanning tree with the second-smallest total weight.

Approach 1: Brute Force O(VE)

For each edge in the MST, remove it and find the MST of the remaining graph. The best such result is the second-best MST.

Approach 2: Efficient O(E log V) or O(V^2)

Build the MST
For each non-MST edge (u, v, w), find the maximum weight edge on the path from u to v in the MST (call it maxW)
The cost of swapping is w - maxW
The second-best MST cost = MST cost + min(w - maxW) over all non-MST edges

Finding max edge on MST path: Use LCA with sparse table to query max edge weight on any path in O(log V).

Visual Example

Non-MST edges and their swap costs:

(A,C,8): Path A-B-D-C in MST, max edge = max(2,3,1) = 3. Swap cost = 8 - 3 = 5
(E,F,9): Path E-B-D-F in MST, max edge = max(5,3,6) = 6. Swap cost = 9 - 6 = 3

Second best MST weight = 17 + min(5, 3) = 20. Achieved by removing (D,F,6) and adding (E,F,9).

Implementation

CPP

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG = 18;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (r[x] < r[y]) swap(x, y);
        p[y] = x;
        if (r[x] == r[y]) r[x]++;
        return true;
    }
};

// Build MST, then find second-best MST
long long secondBestMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);

    vector<vector<pair<int,int>>> adj(n); // MST adjacency list
    vector<bool> inMST(edges.size(), false);
    long long mstWeight = 0;

    // Build MST with Kruskal
    for (int i = 0; i < (int)edges.size(); i++) {
        if (dsu.unite(edges[i].u, edges[i].v)) {
            mstWeight += edges[i].w;
            inMST[i] = true;
            adj[edges[i].u].push_back({edges[i].v, edges[i].w});
            adj[edges[i].v].push_back({edges[i].u, edges[i].w});
        }
    }

    // Build LCA with max edge weight on path
    // up[v][k] = 2^k-th ancestor of v
    // maxEdge[v][k] = max edge weight on path from v to up[v][k]
    vector<vector<int>> up(n, vector<int>(LOG, -1));
    vector<vector<int>> maxEdge(n, vector<int>(LOG, 0));
    vector<int> depth(n, 0);

    // BFS to set up parent and depth
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(0);
    visited[0] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                depth[v] = depth[u] + 1;
                up[v][0] = u;
                maxEdge[v][0] = w;
                q.push(v);
            }
        }
    }

    // Build sparse table
    for (int k = 1; k < LOG; k++) {
        for (int v = 0; v < n; v++) {
            if (up[v][k-1] != -1) {
                up[v][k] = up[up[v][k-1]][k-1];
                maxEdge[v][k] = max(maxEdge[v][k-1],
                                     up[v][k-1] != -1 ? maxEdge[up[v][k-1]][k-1] : 0);
            }
        }
    }

    // Query: max edge weight on path from u to v in MST
    auto queryMaxEdge = [&](int u, int v) -> int {
        int result = 0;
        if (depth[u] < depth[v]) swap(u, v);

        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; k++) {
            if ((diff >> k) & 1) {
                result = max(result, maxEdge[u][k]);
                u = up[u][k];
            }
        }

        if (u == v) return result;

        for (int k = LOG - 1; k >= 0; k--) {
            if (up[u][k] != up[v][k]) {
                result = max(result, max(maxEdge[u][k], maxEdge[v][k]));
                u = up[u][k];
                v = up[v][k];
            }
        }
        result = max(result, max(maxEdge[u][0], maxEdge[v][0]));
        return result;
    };

    // Find second-best MST
    long long secondBest = LLONG_MAX;
    for (int i = 0; i < (int)edges.size(); i++) {
        if (!inMST[i]) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            int maxW = queryMaxEdge(u, v);
            if (w > maxW) { // strict: for second best (not equal)
                secondBest = min(secondBest, mstWeight + w - maxW);
            }
        }
    }

    return secondBest;
}

Strictly Second Best MST

If the second best must be strictly larger (not just a different tree with the same weight), we also need to track the second maximum edge on each path:

CPP

// Track both max and second_max on path
// When swap cost = w - maxW = 0, try w - secondMaxW instead

MST on Complete Graphs

Problem: Min Cost to Connect All Points (LeetCode 1584)

When all pairs of points have edges (complete graph), E = V^2. Use Prim's O(V^2) algorithm (array version) instead of Kruskal's O(V^2 log V).

CPP

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<bool> inMST(n, false);
        vector<int> minDist(n, INT_MAX);
        minDist[0] = 0;

        int totalCost = 0;

        for (int iter = 0; iter < n; iter++) {
            // Find closest non-MST point
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!inMST[j] && (u == -1 || minDist[j] < minDist[u]))
                    u = j;
            }

            inMST[u] = true;
            totalCost += minDist[u];

            // Update distances
            for (int v = 0; v < n; v++) {
                if (!inMST[v]) {
                    int dist = abs(points[u][0] - points[v][0]) +
                               abs(points[u][1] - points[v][1]);
                    minDist[v] = min(minDist[v], dist);
                }
            }
        }
        return totalCost;
    }
};

Classic Problems with Solutions

Problem 1: Min Cost to Connect All Points (LeetCode 1584)

See the complete graph MST section above.

Problem 2: Connecting Cities With Minimum Cost (LeetCode 1135)

Problem: n cities, connections[i] = [city1, city2, cost]. Find minimum cost to connect all cities. Return -1 if impossible.

Approach: Direct application of Kruskal's.

CPP

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        // Convert to edge list
        vector<Edge> edges;
        for (auto& c : connections) {
            edges.push_back({c[0]-1, c[1]-1, c[2]}); // 0-indexed
        }
        sort(edges.begin(), edges.end());

        DSU dsu(n);
        int totalCost = 0, edgeCount = 0;

        for (auto& e : edges) {
            if (dsu.unite(e.u, e.v)) {
                totalCost += e.w;
                edgeCount++;
                if (edgeCount == n - 1) return totalCost;
            }
        }
        return -1; // not connected
    }
};

Problem 3: Optimize Water Distribution in a Village (LeetCode 1168)

Problem: n houses, wells[i] = cost to build a well at house i, pipes[j] = [house1, house2, cost]. Minimize total cost to supply water to all houses.

Key insight: Add a virtual node 0. Connect it to each house i with edge weight wells[i]. Now finding MST of this augmented graph gives the optimal solution.

Why? Building a well at house i = connecting house i directly to the "water source" (node 0). Building a pipe between i and j = connecting them directly. MST minimizes total connection cost.

CPP

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        vector<Edge> edges;

        // Virtual node 0 connected to each house with well cost
        for (int i = 0; i < n; i++) {
            edges.push_back({0, i + 1, wells[i]});
        }

        // Pipe edges
        for (auto& p : pipes) {
            edges.push_back({p[0], p[1], p[2]});
        }

        sort(edges.begin(), edges.end());
        DSU dsu(n + 1); // n+1 nodes (including virtual node 0)

        int totalCost = 0, edgeCount = 0;
        for (auto& e : edges) {
            if (dsu.unite(e.u, e.v)) {
                totalCost += e.w;
                edgeCount++;
                if (edgeCount == n) break; // n edges for n+1 nodes
            }
        }
        return totalCost;
    }
};

Problem 4: Find Critical and Pseudo-Critical Edges in MST (LeetCode 1489)

Problem: Given a weighted undirected graph, find:

Critical edges: edges that appear in ALL MSTs (removing one increases MST weight)
Pseudo-critical edges: edges that appear in SOME but not all MSTs

Approach: For each edge e:

Is e critical? Remove e, compute MST. If MST weight increases (or graph disconnects), e is critical.
Is e pseudo-critical? Force-include e (unite its endpoints first), then compute MST. If MST weight equals original MST weight, e is pseudo-critical.

CPP

class Solution {
public:
    struct DSU {
        vector<int> p, r;
        DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
        int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
        bool unite(int x, int y) {
            x = find(x); y = find(y);
            if (x == y) return false;
            if (r[x] < r[y]) swap(x, y);
            p[y] = x; if (r[x] == r[y]) r[x]++;
            return true;
        }
    };

    // Compute MST weight, optionally excluding edge 'exclude' or force-including 'include'
    int computeMST(int n, vector<vector<int>>& sortedEdges, int exclude, int include) {
        DSU dsu(n);
        int weight = 0, count = 0;

        if (include != -1) {
            auto& e = sortedEdges[include];
            dsu.unite(e[0], e[1]);
            weight += e[2];
            count++;
        }

        for (int i = 0; i < (int)sortedEdges.size(); i++) {
            if (i == exclude) continue;
            auto& e = sortedEdges[i];
            if (dsu.unite(e[0], e[1])) {
                weight += e[2];
                count++;
                if (count == n - 1) break;
            }
        }

        return (count == n - 1) ? weight : INT_MAX;
    }

    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        // Add index to each edge before sorting
        for (int i = 0; i < (int)edges.size(); i++)
            edges[i].push_back(i);

        sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
            return a[2] < b[2];
        });

        int mstWeight = computeMST(n, edges, -1, -1);

        vector<int> critical, pseudo;

        for (int i = 0; i < (int)edges.size(); i++) {
            // Check critical: removing this edge increases MST weight?
            if (computeMST(n, edges, i, -1) > mstWeight) {
                critical.push_back(edges[i][3]); // original index
            }
            // Check pseudo-critical: force-including gives same MST weight?
            else if (computeMST(n, edges, -1, i) == mstWeight) {
                pseudo.push_back(edges[i][3]);
            }
        }

        return {critical, pseudo};
    }
};

Complexity: O(E^2 * alpha(V)) -- for each edge, we run Kruskal's.

MST weight <= optimal TSP tour weight (since removing one edge from tour gives spanning tree)
DFS traversal of MST visits each edge twice -> tour weight <= 2 * MST weight

4. Maze Generation

Generate a random MST of a grid graph to create a maze:

Random edge weights -> random MST -> maze passages
MST guarantees exactly one path between any two cells

Maximum Spanning Tree

Simply negate all edge weights and find MST, or sort edges in descending order in Kruskal's.

CPP

pair<long long, vector<Edge>> maxSpanningTree(int n, vector<Edge>& edges) {
    // Sort by weight descending
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w > b.w;
    });

    DSU dsu(n);
    long long weight = 0;
    vector<Edge> mstEdges;

    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            weight += e.w;
            mstEdges.push_back(e);
            if ((int)mstEdges.size() == n - 1) break;
        }
    }
    return {weight, mstEdges};
}

Minimum Spanning Subgraph (with required edges)

Sometimes certain edges must be included. Force-include them first (unite in DSU), then run Kruskal's on the remaining edges.

Summary

Properties:

Cut property: lightest crossing edge is in MST
Cycle property: heaviest cycle edge is NOT in MST
Unique if all weights distinct
V-1 edges for V vertices
Also a minimum bottleneck spanning tree

Variants:

Maximum spanning tree: negate weights or sort descending
Second best MST: swap one edge using LCA max-edge queries
MST with forced edges: pre-unite in DSU
Steiner tree (MST for subset of vertices): NP-hard in general