A tree is a connected, simple graph with no cycles, such as the below:

N.B. Every connected simple graph has a subgraph which is a tree.

A spanning tree of a graph is a tree which contains all the vertices of the graph (e.g. below the spanning tree is shaded in red.

Exercise

Answers