Graphs / Trees
Least You Need to Know: Trees
A tree is a connected graph with no cycles. In a tree with n vertices, the number of edges is always n-1.
Least you need to know
- A tree is connected and acyclic.
- A graph with n vertices and n-1 edges is a tree if it is connected.
- Adding one edge to a tree creates exactly one cycle.
- Removing one edge from a tree disconnects it.
Key notation
- n — number of vertices
- n-1 — edge count in a tree
- leaf — vertex of degree 1
Worked example
- A tree has 7 vertices.
- Then it has 6 edges.
- If you add one new edge between two existing vertices, you create one cycle.
Common mistakes
- Students often memorize n-1 but forget the graph also has to be connected.
- Students often call any acyclic graph a tree even if it has multiple components.
- Students often forget leaves have degree 1, not 0.
How to recognize it
- If the graph is not connected, it is not a tree.
- Count vertices first, then compare with edges.
- Ask whether there is exactly one simple path between two vertices.
Next recommended lesson
Try Least You Need to Know: Basic Graphs next for a nearby refresher.
Least You Need to Know: Basic GraphsRelated lessons
Keep going with nearby lessons in the same topic.