Discrete Math › Section C · Graph theory › Topic C.2
Trees and their properties
A tree is the leanest way to hold a set of vertices together: connected, but with no edge to spare. That simple definition produces a remarkable list of facts, from an exact edge count to unique routes between vertices, and trees turn up everywhere from folder systems to sorting.
In this topic
- Connected, with no cycles
- Exactly one path between any two vertices
- Every tree has leaves
- A tree with n vertices has n − 1 edges
- Worked example: counting leaves
- Three properties, any two will do
- Rooted trees
- Binary trees
- Worked example: three traversals
- How many trees are there?
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…