Computer Science & Data Science · Graphs and algorithms

Minimum spanning tree

A minimum spanning tree connects every vertex of a connected, undirected, weighted graph with the minimum total edge weight.

AdvancedUniversity/collegeBachelor foundations

Create flashcards or a quiz I already have an account

Free to browse · flashcards or a multiple-choice quiz · import from Essential

Formula

T^{*} \in ar g T \in T (G) min e \in T \sum w (e), ∣ E (T^{*}) ∣ = ∣ V ∣ - 1

w(e) is an additive edge cost; a spanning tree on |V| vertices has exactly |V|−1 edges.

Variables & units

Variables & units
Symbol	Meaning	Unit
$G=(V,E)$	Connected undirected graph	nodes and edges
$T$	A spanning tree connecting every vertex without a cycle	edge set
$w(e)$	Weight of edge e	cost per edge
T*	A spanning tree with minimum total weight	edge set

LaTeX

T^*\in\arg\min_{T\in\mathcal T(G)}\sum_{e\in T}w(e),\quad |E(T^*)|=|V|-1

QUANTA STUDYquanta-study.de

Undirected graph with four vertices and five edges. AB of weight 1, BC of 2, and CD of 3 form the highlighted minimum spanning tree. AC of 4 and BD of 5 are dashed because each would close a cycle during Kruskal’s algorithm. The total weight is 6. — Kruskal selects AB=1, BC=2, and CD=3. The three edges connect four vertices without a cycle and have total weight 6.

Derivation & background

A spanning tree contains all vertices, is connected and has no cycles; therefore it has exactly |V|−1 edges. A minimum spanning tree minimizes the sum of their weights, not the longest individual path or paths from one chosen start vertex. Kruskal sorts edges by weight and accepts an edge only if it does not create a cycle; Prim repeatedly adds a least-weight edge crossing the current cut. Tied weights can yield several equally light spanning trees. A disconnected graph instead has a minimum spanning forest.

Exam blueprint

Validity range

Derivation steps

A minimum spanning tree connects all vertices without cycles at the lowest possible total weight.

1Sort the edges by weight.
2Add the next edge only if it does not create a cycle.
3With four vertices, stop after selecting three edges; the tree is then connected.

Rearrangements

Number of edges in a spanning tree

|E(T)|=|V|-1

Applies to every spanning tree of a connected graph.

Task variant

Apply Kruskal: which edges do you choose for AB=1, BC=2, CD=3, AC=4, BD=5, and what is the total weight?

Kruskal selects AB=1, BC=2 and CD=3.
The four vertices are connected without a cycle; total weight is 1+2+3=6.

Common mistakes

Confusing a minimum spanning tree with shortest paths from a starting vertex.

A spanning tree minimizes the sum of all selected edges and has no designated starting vertex.

Exam context

Design low-cost connected networks such as utility, road, or communication networks.

Formula cluster

Graphs and algorithms

A minimum spanning tree connects every vertex of a connected, undirected, weighted graph with the minimum total edge weight.

BFS: distance layers and shortest paths; BFS/DFS: O(|V|+|E|)

Graph search: BFS, DFS and shortest paths

Kürzester Pfad: min Σw(e); Relaxation: d(v) ← min(d(v), d(u)+w(u,v))

Dijkstra’s algorithm for weighted shortest paths

f(n) ∈ O(g(n))

Big-O notation (asymptotic upper bound)

Worked example

For edges AB=1, BC=2, CD=3, AC=4, and BD=5, Kruskal selects AB, BC, and CD. The three edges connect four vertices without a cycle; their total weight is 1+2+3=6. Check: replacing BC with AC gives 1+4+3=8, and any connection using BD costs at least 8.

Applications

Design low-cost connected networks such as utility, road, or communication networks.

How do you calculate with Minimum spanning tree?

Here is how to work through a typical Minimum spanning tree (Connect all vertices with minimum total edge weight and |V|−1 edges.) task step by step:

1
Task
Apply Kruskal: which edges do you choose for AB=1, BC=2, CD=3, AC=4, BD=5, and what is the total weight?
Solution path
1. Kruskal selects AB=1, BC=2 and CD=3.
2. The four vertices are connected without a cycle; total weight is 1+2+3=6.

Frequently asked questions about Minimum spanning tree

What does Minimum spanning tree describe?+

The relation T^*\in\arg\min_{T\in\mathcal T(G)}\sum_{e\in T}w(e),\quad |E(T^*)|=|V|-1 describes A minimum spanning tree connects every vertex of a connected, undirected, weighted graph with the minimum total edge weight. In the example For edges AB=1, BC=2, CD=3, AC=4, and BD=5, Kruskal selects AB, BC, and CD. It applies under the assumptions stated in the background. Validity limit: A spanning tree contains all vertices, is connected and has no cycles; therefore it has exactly |V|−1 edges. A minimum spanning tree minimizes the sum of their weights, not the Source: MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II.

How should I work through a calculation?+

First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example For edges AB=1, BC=2, CD=3, AC=4, and BD=5, Kruskal selects AB, BC, and CD. The three edges connect four vertices without a cycle; their total weight is 1+2+3=6. Check: replacing BC with AC gives 1+4+3=8, and any connection using BD costs at least 8. provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: A spanning tree contains all vertices, is connected and has no cycles; therefore it has exactly |V|−1 edges. A minimum spanning tree minimizes the sum of their weights, not the Source: MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II.

Which assumption must I keep in mind?+

The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: A spanning tree contains all vertices, is connected and has no cycles; therefore it has exactly |V|−1 edges. A minimum spanning tree minimizes the sum of their weights, not the Source: MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II.

Which units and quantities are involved?+

The stated units are: w(e) is an additive edge cost; a spanning tree on |V| vertices has exactly |V|−1 edges.. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: A spanning tree contains all vertices, is connected and has no cycles; therefore it has exactly |V|−1 edges. A minimum spanning tree minimizes the sum of their weights, not the Source: MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II.

When is comparison with graphsuche-bfs-dfs-kuerzeste-wege and dijkstra-kuerzeste-wege useful?+

Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: A spanning tree contains all vertices, is connected and has no cycles; therefore it has exactly |V|−1 edges. A minimum spanning tree minimizes the sum of their weights, not the Source: MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II.

Quanta exam set

Curated exam set for "Minimum spanning tree":

Question (front)

Which formula describes Minimum spanning tree?

Answer in your set

Question (front)

How do you rearrange Minimum spanning tree for Number of edges in a spanning tree?

Answer in your set

Question (front)

Which common mistake happens with Minimum spanning tree?

Answer in your set

+ 7 more cards: units, variables, derivation, example, exam task

The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.

Create flashcards or a quiz I already have an account

Subject references and further reading

This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.

[1]MIT OpenCourseWare 6.046J, Lectures 3–4: Minimum Spanning Trees I–II.

More formulas: Algorithms, number representation and cryptography

x=-b_{N-1}2^{N-1}+\sum_{i=0}^{N-2}b_i2^i

Two’s-complement signed integer

T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1)

Divide-and-conquer runtime recurrence

x=(-1)^s\begin{cases}(1+f)2^{E-b},&0<E<2^w-1\\f2^{1-b},&E=0\end{cases}

IEEE 754 floating-point representation and rounding

\neg(A\land B)=\neg A\lor\neg B,\quad\neg(A\lor B)=\neg A\land\neg B

Boolean algebra identities and De Morgan laws

Spaced-repetition apps

Compare scheduling workflows

Study evidence

Read methods, results and limits

Compare flashcard apps

FSRS support and study features

Create a formula exam set

From Essential in Quanta

Retain Minimum spanning tree for exams

Create a curated FSRS exam set for Connect all vertices with minimum total edge weight and |V|−1 edges.: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.

Create flashcards or a quiz Already registered? Continue directly

Curated formula set · LaTeX · FSRS spaced repetition · import from Essential

Quanta Study editorial team

Minimum spanning tree

A minimum spanning tree connects every vertex of a connected, undirected, weighted graph with the minimum total edge weight.

AdvancedUniversity/collegeBachelor foundations

Free to browse · flashcards or a multiple-choice quiz · import from Essential

Symbol

Meaning

Unit

G=(V,E)

Connected undirected graph

nodes and edges

T

A spanning tree connecting every vertex without a cycle

edge set

w(e)

Weight of edge e

cost per edge

A spanning tree with minimum total weight

edge set

Derivation & background

Exam blueprint

Validity range

Derivation steps

A minimum spanning tree connects all vertices without cycles at the lowest possible total weight.

1Sort the edges by weight.
2Add the next edge only if it does not create a cycle.
3With four vertices, stop after selecting three edges; the tree is then connected.

How do you calculate with Minimum spanning tree?

Here is how to work through a typical Minimum spanning tree (Connect all vertices with minimum total edge weight and |V|−1 edges.) task step by step:

Task

Apply Kruskal: which edges do you choose for AB=1, BC=2, CD=3, AC=4, BD=5, and what is the total weight?

Solution path

Kruskal selects AB=1, BC=2 and CD=3.
The four vertices are connected without a cycle; total weight is 1+2+3=6.

Frequently asked questions about Minimum spanning tree

What does Minimum spanning tree describe?+

How should I work through a calculation?+

Which assumption must I keep in mind?+

Which units and quantities are involved?+

When is comparison with graphsuche-bfs-dfs-kuerzeste-wege and dijkstra-kuerzeste-wege useful?+

Retain Minimum spanning tree for exams

Curated formula set · LaTeX · FSRS spaced repetition · import from Essential