Go to content

Summary/Background

A tree is a connected graph with no cycles. A spanning tree is a subgraph which includes all the vertices of a graph and is also a tree. A minimum spanning tree (or minimum connector) is a spanning tree such that the total length of its edges is as small as possible.
Note: The number of edges in the minimum spanning tree is one less than the number of vertices.

Software/Applets used on this page

Helen Foster
This page uses Macromedia Flash. Your browser will need to have the Flash plugin installed - freely available from Macromedia. Flash movies designed by Helen Foster, Alton College, UK, and used with her permission.

Glossary

connected

of two vertices if there is a path between them.

graph

A diagram showing a relationship between two variables.
The diagram shows a vertical y axis and a horizontal x axis.

minimum spanning tree

A spanning tree such that the total length of its edges is as small as possible.

spanning tree

A subgraph which includes all the vertices of a graph and is also a tree.

tree

A connected graph with no cycles.

Full Glossary List

This question appears in the following syllabi:

SyllabusModuleSectionTopicExam Year
AQA A-Level (UK - Pre-2017)D1Algorithms on graphsMinimum connector-
Edexcel A-Level (UK - Pre-2017)D1Algorithms on graphsMinimum connector-
I.B. Higher Level10Algorithms on graphsMinimum connector-
OCR A-Level (UK - Pre-2017)D1Algorithms on graphsMinimum connector-
OCR-MEI A-Level (UK - Pre-2017)D1Algorithms on graphsMinimum connector-
Universal (all site questions)AAlgorithms on graphsMinimum connector-
Edexcel AS Further Maths 2017Decision Maths 1Algorithms on GraphsMinimum Connector-
AQA AS Further Maths 2017Discrete MathsNetworksMinimum Connector-
OCR AS Further Maths 2017Discrete MathsNetwork AlgorithmsMinimum Connector-
OCR MEI AS Further Maths 2017Modelling with AlgorithmsNetworksMinimum Connector-
Edexcel AS/A2 Further Maths 2017Decision Maths 1Algorithms on GraphsMinimum Connector-
AQA AS/A2 Further Maths 2017Discrete MathsNetworksMinimum Connector-