Network in Graph Theory
Tree
A connected network with no cycles.
| English | Tree |
|---|---|
| Bahasa Melayu | Pokok |
| 中文 | 树 |
How it is used
Four towns A, B, C and D connected as A–B, B–C and B–D form a tree, because they are all connected yet contain no cycle. A tree with n vertices always has exactly n − 1 edges, so 4 towns need 4 − 1 = 3 roads.
Where it shows up in SPM
Appears in the Network in Graph Theory chapter (Form 5). Paper 2 may ask you to identify or draw a tree, or to find the least number of edges needed to connect all vertices, using the fact that a tree with n vertices has n − 1 edges.
Don't confuse it with
Open the chapter: Network in Graph Theory →
Frequently asked questions
How can I tell if a network is a tree?
Check two things: the network must be connected, meaning you can reach every vertex from any other, and it must have no cycle, meaning no closed loop of edges. If both hold, it is a tree, and it will have exactly one edge fewer than its number of vertices.
Why does a tree with n vertices have n − 1 edges?
Starting from one vertex, each new edge you add brings in exactly one new vertex without forming a cycle. To connect n vertices this way you need n − 1 edges; adding any further edge would create a cycle and break the tree.