36.01Intermediate / Advanced5 topics17 min5 interactive animations

MST definitions

A minimum spanning tree connects all vertices of a weighted graph with n - 1 edges of the smallest total weight; the cut property and the cycle property say which edges can belong to one.

Learning goals

Recognise a spanning tree and compute its total weight
State and apply the cut property and the cycle property
Decide whether an edge can be in, or must be in, a minimum spanning tree
Explain when the minimum spanning tree is unique

Prerequisites

Graph representationsConnected componentsUnion-find

Laying cable between towns, wiring a circuit board, building a road network: connect every point as cheaply as possible, with no pointless loops. The answer is a minimum spanning tree.

36.01.1

Spanning tree

A **spanning tree** of a connected undirected graph is a subset of its edges that connects every vertex and has no cycle. Such a subset always has exactly n - 1 edges: fewer cannot connect everything, and one more would close a cycle. Check a candidate by adding its edges one at a time with union-find; a cycle is detected when both ends already share a root.

A graph usually has many spanning trees. A graph that is not connected has none, only a **spanning forest** with one tree for each component. The first animation option, Kruskal, builds a tree edge by edge on the preset graph.

Java

1static boolean isSpanningTree(int n, int[][] edges, int[] chosen) {   // chosen = indexes into edges
2    if (chosen.length != n - 1) return false;
3    int[] parent = new int[n];
4    for (int i = 0; i < n; i++) parent[i] = i;
5    for (int k : chosen) {
6        int a = find(parent, edges[k][0]), b = find(parent, edges[k][1]);
7        if (a == b) return false;                          // a cycle (or the same edge twice)
8        parent[a] = b;
9    }
10    return true;                                           // n - 1 edges and no cycle: connected
11}
12static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Minimum spanning tree: Kruskal and Prim (lazy and eager)

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

Edge / vertex being consideredIn the treeRejected (would close a cycle)In the heap or frontier

edges, lightest first

1-2:1

1-3:2

0-2:3

0-1:4

2-3:4

2-4:5

4-5:6

3-4:7

component leader of v

Setup

Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.

Step 1 / 10

Java

1static long kruskal(int n, int[][] edges) {          // edges {u, v, w}; total weight of the minimum spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));   // lightest first
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    long total = 0;
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                           // already connected: this edge would close a cycle
10        parent[a] = b;
11        total += e[2];
12    }
13    return total;
14}
15static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
16static long primLazy(int n, List<int[]>[] adj, int s) {   // adj[u] = {v, w}; weight of the tree of s's component
17    boolean[] in = new boolean[n];
18    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // {vertex, weight of the edge that reaches it}
19    pq.add(new int[]{s, 0});
20    long total = 0;
21    while (!pq.isEmpty()) {
22        int[] top = pq.poll();
23        if (in[top[0]]) continue;                       // outdated: already in the tree
24        in[top[0]] = true;
25        total += top[1];
26        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
27    }
28    return total;
29}
30static long primEager(int n, List<int[]>[] adj, int s) {   // key[v] = cheapest edge from the tree to v
31    long INF = Long.MAX_VALUE / 2;
32    long[] key = new long[n];
33    Arrays.fill(key, INF);
34    key[s] = 0;
35    boolean[] in = new boolean[n];
36    long total = 0;
37    for (int step = 0; step < n; step++) {
38        int u = -1;
39        for (int v = 0; v < n; v++) if (!in[v] && key[v] < INF && (u == -1 || key[v] < key[u])) u = v;
40        if (u == -1) break;                             // the rest is unreachable
41        in[u] = true;
42        total += key[u];
43        for (int[] e : adj[u]) if (!in[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // decrease key
44    }
45    return total;
46}

Live state

0 edges examined0 edges rejected

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The tree has 5 edges and total weight 17 (the smallest possible).

36.01.2

Total weight

The **weight** of a spanning tree is the sum of its edge weights. A **minimum spanning tree** (MST) is a spanning tree of smallest weight; a maximum spanning tree is defined the same way with the largest. Two different trees can have the same weight, so the minimum tree is not always unique, but the minimum *weight* is.

For a graph with a handful of edges you can list every spanning tree and sort the weights. This is far too slow for real inputs (the number of spanning trees grows very fast), but it is the definition made concrete, and it is what the tests use as a baseline.

Java

1static List<Long> allSpanningTreeWeights(int n, int[][] edges) {   // every spanning tree, smallest first; tiny graphs only
2    List<Long> weights = new ArrayList<>();
3    int m = edges.length;
4    for (int mask = 0; mask < (1 << m); mask++) {
5        if (Integer.bitCount(mask) != n - 1) continue;
6        int[] parent = new int[n];
7        for (int i = 0; i < n; i++) parent[i] = i;
8        long w = 0;
9        boolean ok = true;
10        for (int k = 0; k < m && ok; k++) {
11            if ((mask >> k & 1) == 0) continue;
12            int a = find(parent, edges[k][0]), b = find(parent, edges[k][1]);
13            if (a == b) ok = false; else { parent[a] = b; w += edges[k][2]; }
14        }
15        if (ok) weights.add(w);
16    }
17    Collections.sort(weights);
18    return weights;
19}
20static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Minimum spanning tree: Kruskal and Prim (lazy and eager)

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

Edge / vertex being consideredIn the treeRejected (would close a cycle)In the heap or frontier

edges, lightest first

1-2:1

1-3:2

0-2:3

0-1:4

2-3:4

2-4:5

4-5:6

3-4:7

component leader of v

Setup

Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.

Step 1 / 10

Java

1static long kruskal(int n, int[][] edges) {          // edges {u, v, w}; total weight of the minimum spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));   // lightest first
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    long total = 0;
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                           // already connected: this edge would close a cycle
10        parent[a] = b;
11        total += e[2];
12    }
13    return total;
14}
15static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
16static long primLazy(int n, List<int[]>[] adj, int s) {   // adj[u] = {v, w}; weight of the tree of s's component
17    boolean[] in = new boolean[n];
18    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // {vertex, weight of the edge that reaches it}
19    pq.add(new int[]{s, 0});
20    long total = 0;
21    while (!pq.isEmpty()) {
22        int[] top = pq.poll();
23        if (in[top[0]]) continue;                       // outdated: already in the tree
24        in[top[0]] = true;
25        total += top[1];
26        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
27    }
28    return total;
29}
30static long primEager(int n, List<int[]>[] adj, int s) {   // key[v] = cheapest edge from the tree to v
31    long INF = Long.MAX_VALUE / 2;
32    long[] key = new long[n];
33    Arrays.fill(key, INF);
34    key[s] = 0;
35    boolean[] in = new boolean[n];
36    long total = 0;
37    for (int step = 0; step < n; step++) {
38        int u = -1;
39        for (int v = 0; v < n; v++) if (!in[v] && key[v] < INF && (u == -1 || key[v] < key[u])) u = v;
40        if (u == -1) break;                             // the rest is unreachable
41        in[u] = true;
42        total += key[u];
43        for (int[] e : adj[u]) if (!in[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // decrease key
44    }
45    return total;
46}

Live state

0 edges examined0 edges rejected

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The tree has 5 edges and total weight 17 (the smallest possible).

36.01.3

Cut property

A **cut** splits the vertices into two non-empty sets S and the rest; an edge **crosses** the cut when its ends are on different sides. The **cut property**: the lightest edge crossing any cut belongs to some minimum spanning tree. Reason: take any MST; it must cross the cut somewhere. If it does not use the lightest crossing edge e, add e (this creates a cycle that crosses the cut again) and remove another crossing edge of that cycle, which is at least as heavy. The weight does not increase.

Kruskal and Prim are both repeated applications of this one fact. Run the *Cut property* option of the variations animation with different cut sizes and read the crossing edges.

Java

1static int lightestAcrossCut(int[][] edges, boolean[] inS) {   // index of a lightest edge with exactly one end in S, or -1
2    int best = -1;
3    for (int k = 0; k < edges.length; k++) {
4        if (inS[edges[k][0]] == inS[edges[k][1]]) continue;   // both ends on the same side: not crossing
5        if (best == -1 || edges[k][2] < edges[best][2]) best = k;
6    }
7    return best;
8}

MST properties and variations: cut, cycle, second best, critical edges

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Being examinedIn the minimum spanning treeSide S of the cutHeaviest edge on the path (the swap)Not in the tree

side S

Setup

A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.

Step 1 / 3

Java

1static long secondBestMst(int n, int[][] edges) {   // connected graph; Long.MAX_VALUE when no other spanning tree exists
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    boolean[] inTree = new boolean[sorted.length];
7    List<int[]>[] tree = new List[n];
8    for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
9    long total = 0;
10    for (int i = 0; i < sorted.length; i++) {
11        int a = find(parent, sorted[i][0]), b = find(parent, sorted[i][1]);
12        if (a == b) continue;
13        parent[a] = b; inTree[i] = true; total += sorted[i][2];
14        tree[sorted[i][0]].add(new int[]{sorted[i][1], sorted[i][2]});
15        tree[sorted[i][1]].add(new int[]{sorted[i][0], sorted[i][2]});
16    }
17    long best = Long.MAX_VALUE;
18    for (int i = 0; i < sorted.length; i++) {
19        if (inTree[i]) continue;
20        int heaviest = maxOnPath(tree, sorted[i][0], sorted[i][1], -1);   // the swap removes the heaviest tree edge on the cycle
21        best = Math.min(best, total - heaviest + sorted[i][2]);
22    }
23    return best;
24}
25static List<List<Integer>> criticalEdges(int n, int[][] edges) {   // {critical, pseudo-critical} edge indexes
26    long base = mst(n, edges, -1, -1);
27    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
28    for (int i = 0; i < edges.length; i++) {
29        if (mst(n, edges, i, -1) > base) critical.add(i);          // without it the tree is heavier or breaks
30        else if (mst(n, edges, -1, i) == base) pseudo.add(i);      // forced in, still minimum
31    }
32    return List.of(critical, pseudo);
33}

Live state

0 edges examined

0..1

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	S=0..1	A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.
2	L1	crossing=3	3 edges cross the cut: 0-2:3, 1-2:1, 1-3:2.
3	L1	return=1-2:1 tree contains it=yes	The cut property: the lightest crossing edge, 1-2:1, belongs to some minimum spanning tree. Reason: any tree must cross the cut somewhere; swapping a heavier crossing edge for this one keeps it a tree and cannot raise the weight. Kruskal's tree contains it.

36.01.4

Cycle property

The **cycle property**: if an edge is the heaviest edge on some cycle, and strictly heavier than every other edge of that cycle, it is in no minimum spanning tree. (With ties, a heaviest edge may be dropped, but some tree may still use it.) Every edge that Kruskal rejects is the heaviest on the cycle it would close, which is why rejecting it is safe.

Put as a test: an edge (u, v) of weight w is in *some* MST exactly when u and v are not already connected by edges of weight less than w. It is in *every* MST exactly when they are not connected by the other edges of weight at most w. The *Cycle property* option lists each rejected edge with its cycle.

Java

1static boolean canBeInMst(int n, int[][] edges, int k) {          // in some minimum spanning tree of a connected graph
2    return !connectedUsing(n, edges, edges[k][0], edges[k][1], edges[k][2] - 1, -1);   // joined by edges lighter than w? then no
3}
4static boolean mustBeInMst(int n, int[][] edges, int k) {         // in every minimum spanning tree
5    return !connectedUsing(n, edges, edges[k][0], edges[k][1], edges[k][2], k);        // joined by the other edges of weight <= w? then no
6}
7static boolean connectedUsing(int n, int[][] edges, int a, int b, int maxWeight, int skip) {
8    int[] parent = new int[n];
9    for (int i = 0; i < n; i++) parent[i] = i;
10    for (int k = 0; k < edges.length; k++)
11        if (k != skip && edges[k][2] <= maxWeight) parent[find(parent, edges[k][0])] = find(parent, edges[k][1]);
12    return find(parent, a) == find(parent, b);
13}
14static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

MST properties and variations: cut, cycle, second best, critical edges

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Being examinedIn the minimum spanning treeSide S of the cutHeaviest edge on the path (the swap)Not in the tree

side S

Setup

A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.

Step 1 / 3

Java

1static long secondBestMst(int n, int[][] edges) {   // connected graph; Long.MAX_VALUE when no other spanning tree exists
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    boolean[] inTree = new boolean[sorted.length];
7    List<int[]>[] tree = new List[n];
8    for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
9    long total = 0;
10    for (int i = 0; i < sorted.length; i++) {
11        int a = find(parent, sorted[i][0]), b = find(parent, sorted[i][1]);
12        if (a == b) continue;
13        parent[a] = b; inTree[i] = true; total += sorted[i][2];
14        tree[sorted[i][0]].add(new int[]{sorted[i][1], sorted[i][2]});
15        tree[sorted[i][1]].add(new int[]{sorted[i][0], sorted[i][2]});
16    }
17    long best = Long.MAX_VALUE;
18    for (int i = 0; i < sorted.length; i++) {
19        if (inTree[i]) continue;
20        int heaviest = maxOnPath(tree, sorted[i][0], sorted[i][1], -1);   // the swap removes the heaviest tree edge on the cycle
21        best = Math.min(best, total - heaviest + sorted[i][2]);
22    }
23    return best;
24}
25static List<List<Integer>> criticalEdges(int n, int[][] edges) {   // {critical, pseudo-critical} edge indexes
26    long base = mst(n, edges, -1, -1);
27    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
28    for (int i = 0; i < edges.length; i++) {
29        if (mst(n, edges, i, -1) > base) critical.add(i);          // without it the tree is heavier or breaks
30        else if (mst(n, edges, -1, i) == base) pseudo.add(i);      // forced in, still minimum
31    }
32    return List.of(critical, pseudo);
33}

Live state

0 edges examined

0..1

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	S=0..1	A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.
2	L1	crossing=3	3 edges cross the cut: 0-2:3, 1-2:1, 1-3:2.
3	L1	return=1-2:1 tree contains it=yes	The cut property: the lightest crossing edge, 1-2:1, belongs to some minimum spanning tree. Reason: any tree must cross the cut somewhere; swapping a heavier crossing edge for this one keeps it a tree and cannot raise the weight. Kruskal's tree contains it.

36.01.5

Uniqueness with distinct weights

If all edge weights are different, the minimum spanning tree is **unique**. Equal weights are what create choices: an edge is an alternative to another only when they tie. Using the tests above, an MST is unique exactly when no edge is in some but not all minimum trees (no *pseudo-critical* edge).

Distinct weights make that impossible, because an edge that is in some MST but not all would need another edge of equal weight to swap with. The last variations option lists critical and pseudo-critical edges; its first preset has ties and so has pseudo-critical edges.

Java

1static boolean mstIsUnique(int n, int[][] edges) {                // connected graph
2    for (int k = 0; k < edges.length; k++) {
3        boolean can = !connectedUsing(n, edges, edges[k][0], edges[k][1], edges[k][2] - 1, -1);
4        boolean must = !connectedUsing(n, edges, edges[k][0], edges[k][1], edges[k][2], k);
5        if (can && !must) return false;                            // in some minimum trees but not all: a choice exists
6    }
7    return true;
8}
9static boolean connectedUsing(int n, int[][] edges, int a, int b, int maxWeight, int skip) {
10    int[] parent = new int[n];
11    for (int i = 0; i < n; i++) parent[i] = i;
12    for (int k = 0; k < edges.length; k++)
13        if (k != skip && edges[k][2] <= maxWeight) parent[find(parent, edges[k][0])] = find(parent, edges[k][1]);
14    return find(parent, a) == find(parent, b);
15}
16static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

MST properties and variations: cut, cycle, second best, critical edges

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Being examinedIn the minimum spanning treeSide S of the cutHeaviest edge on the path (the swap)Not in the tree

side S

Setup

A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.

Step 1 / 3

Java

1static long secondBestMst(int n, int[][] edges) {   // connected graph; Long.MAX_VALUE when no other spanning tree exists
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    boolean[] inTree = new boolean[sorted.length];
7    List<int[]>[] tree = new List[n];
8    for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
9    long total = 0;
10    for (int i = 0; i < sorted.length; i++) {
11        int a = find(parent, sorted[i][0]), b = find(parent, sorted[i][1]);
12        if (a == b) continue;
13        parent[a] = b; inTree[i] = true; total += sorted[i][2];
14        tree[sorted[i][0]].add(new int[]{sorted[i][1], sorted[i][2]});
15        tree[sorted[i][1]].add(new int[]{sorted[i][0], sorted[i][2]});
16    }
17    long best = Long.MAX_VALUE;
18    for (int i = 0; i < sorted.length; i++) {
19        if (inTree[i]) continue;
20        int heaviest = maxOnPath(tree, sorted[i][0], sorted[i][1], -1);   // the swap removes the heaviest tree edge on the cycle
21        best = Math.min(best, total - heaviest + sorted[i][2]);
22    }
23    return best;
24}
25static List<List<Integer>> criticalEdges(int n, int[][] edges) {   // {critical, pseudo-critical} edge indexes
26    long base = mst(n, edges, -1, -1);
27    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
28    for (int i = 0; i < edges.length; i++) {
29        if (mst(n, edges, i, -1) > base) critical.add(i);          // without it the tree is heavier or breaks
30        else if (mst(n, edges, -1, i) == base) pseudo.add(i);      // forced in, still minimum
31    }
32    return List.of(critical, pseudo);
33}

Live state

0 edges examined

0..1

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	S=0..1	A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.
2	L1	crossing=3	3 edges cross the cut: 0-2:3, 1-2:1, 1-3:2.
3	L1	return=1-2:1 tree contains it=yes	The cut property: the lightest crossing edge, 1-2:1, belongs to some minimum spanning tree. Reason: any tree must cross the cut somewhere; swapping a heavier crossing edge for this one keeps it a tree and cannot raise the weight. Kruskal's tree contains it.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Min Cost to Connect All Points
Connecting Cities With Minimum Cost

Advanced

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Optimize Water Distribution in a Village

Key takeaways

A spanning tree connects all n vertices with n - 1 edges and no cycle; a disconnected graph has only a spanning forest.
Cut property: a lightest edge across any cut is in some MST. Cycle property: a strictly heaviest edge of a cycle is in no MST.
An edge is in some MST iff its ends are not joined by strictly lighter edges.
Distinct weights guarantee a unique MST; equal weights are what create choices.