Trees & their properties
A tree is a connected acyclic graph, and several very different-looking conditions are equivalent to it: connected with n − 1 edges, acyclic with n − 1 edges, or having a unique path between every pair of vertices. Every tree with at least two vertices has at least two leaves, which is what makes induction on trees work — remove a leaf and you still have a tree.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Use the edge identityA tree on n vertices has exactly n − 1 edges. Any two of {connected, acyclic, n − 1 edges} imply the third.
- Combine with the handshake lemmaΣ deg(v) = 2(n − 1) in a tree, which pins down degree sequences tightly.
- Peel leaves for inductionRemoving a leaf from a tree leaves a tree with one fewer vertex and edge — the standard induction step.
- Check uniqueness of pathsTwo distinct paths between the same pair would create a cycle, so path uniqueness characterises trees.
Worked example
A tree has 10 vertices, and every vertex has degree 1 or 3. How many leaves does it have?
- Edges: 10 − 1 = 9, so Σ deg = 18.
- Let L be the number of leaves and T the number of degree-3 vertices, with L + T = 10.
- Degrees: L + 3T = 18.
- Subtracting: 2T = 8, so T = 4 and L = 6.
Answer. 6 leaves and 4 vertices of degree 3.
Where marks get dropped
These are the specific errors that cost credit on trees & their properties questions — QED's rubric penalises each of them separately.
- Using n − 1 edges alone as proof of a tree. A triangle plus an isolated vertex has 4 vertices and 3 edges but is neither connected nor acyclic.
- Forgetting that a single vertex is a tree, with 0 edges — the identity still holds.
- Assuming every tree has a vertex of high degree. A path is a tree where every internal vertex has degree exactly 2.
Practise this until it is automatic
Unlimited fresh questions
QED generates new trees & their properties problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.
Trees & their properties — frequently asked questions
Why does every tree have at least two leaves?
Take a longest path; its two endpoints can have no other neighbours, or the path could be extended or a cycle formed. So both ends are leaves.
How many labelled trees are there on n vertices?
n^(n−2), by Cayley’s formula. For n = 4 that is 16, proved elegantly via Prüfer sequences.
What is a forest?
A disjoint union of trees — acyclic but possibly disconnected. A forest with n vertices and c components has exactly n − c edges.
The rest of Graphs
Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Degrees & the handshake lemma
- 2Paths, cycles, connectivity & components
- 3Trees & their properties
- 4Bipartite graphs & colouring basics
- 5Euler & Hamilton paths and circuits
- 6Adjacency matrices & isomorphism
- 7Degree sequences & graphic sequences
- 8Spanning trees: Kruskal & Prim
- 9Shortest paths with Dijkstra
- 10Planarity & Euler’s formula
- 11Directed graphs, in-degree & out-degree
- 12Binary trees: height, traversals & counting
- 13Chromatic number & colouring bounds
- 14Matchings & Hall’s marriage theorem
Ready to make trees & their properties exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →