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.

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-