Trees and Spanning Trees
Characterise a tree in several equivalent ways, prove the edge count, and count the labelled trees on n vertices.
What a learner can do afterwards
- Prove that connected with n minus one edges, acyclic and connected, and unique paths are the same condition
- Show every connected graph has a spanning tree
- State Cayley's formula and outline one argument for it
1 · Read
A tree is a connected graph with no cycles. Three descriptions coincide: connected with n minus 1 edges, acyclic and connected, and exactly one path between every pair of vertices. Each viewpoint makes a different fact obvious, so learn to switch between them.
A tree on n vertices always has n minus 1 edges, so a tree with 9 vertices has 8 edges. Adding any missing edge closes exactly one cycle, and removing any edge disconnects the tree.
A spanning tree keeps every vertex while trimming edges to the treelike minimum. Prune cycles one edge at a time and the process always succeeds, so every connected graph has a spanning tree. Networks love them because they connect everything with the fewest edges.
Cayley counted the labelled trees: n to the power (n minus 2) on n vertices. That gives 16 trees on 4 vertices and 125 on 5, so the family grows fast.
Spot a tree by any of its three faces, count edges as vertices minus one, and count labelled trees with Cayley.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.