A Reusable Induction Step for Trees
Many proofs about trees become simpler after removing one vertex. The useful choice is a leaf: deleting it reduces the number of vertices by exactly one, while the remaining graph is still a tree. An induction proof then has two tasks. First, establish the claim for the one-vertex tree. Second, explain how the claim for the smaller tree changes when the deleted leaf and its incident edge are restored. The second task is where the details of a proof usually lie.
The empty graph is not a tree under this definition: it is not connected. The smallest tree therefore has order \(1\). These conventions matter because a leaf-deletion induction reduces a tree of order \(n\ge2\) to one of order \(n-1\), and the final graph is a singleton rather than an empty graph.
Proof. Let \(T\) have at least two vertices. Since it is connected, it has a path, and because it is finite there is a path of maximum length. Let \(x\) be one endpoint. The vertex \(x\) has a neighbor, namely the next vertex on the path. It cannot have a neighbor outside the path, since that would extend the path. It cannot have a neighbor on the path other than its next vertex: such an edge, together with the segment of the path between the two vertices, would form a cycle. Thus \(x\) has degree \(1\), so it is a leaf.
Now delete a leaf \(x\) and its incident edge. No cycle can be created by deleting vertices or edges, so \(T-x\) is acyclic. To check connectedness, take any two vertices \(u,v\) that remain. Since \(T\) is connected, there is a path from \(u\) to \(v\). A leaf cannot be an internal vertex of a path, because an internal vertex is incident with two path edges, whereas \(x\) has degree \(1\). As neither endpoint is \(x\), the path avoids \(x\); it is still present in \(T-x\). Hence \(T-x\) is connected and is a tree. If \(T\) has two vertices, this remaining tree is the one-vertex tree. If \(T\) has more than two vertices, no remaining vertex is isolated: a remaining vertex whose only neighbor was \(x\) would have no connection to any other remaining vertex in \(T\), contradicting the connectedness of \(T\). \(\square\)
The Induction Template
Let \(P(T)\) be a statement about finite trees. Induction on the order means proving the claim for every possible order, starting at \(n=1\). At the induction step, assume the claim for every tree of order \(n-1\), take a tree \(T\) of order \(n\), and choose a leaf \(x\). The lemma gives a smaller tree \(T-x\), so the induction hypothesis applies. The proof must then account for the neighbor of \(x\), the deleted edge, and any change to the quantity or structure being studied.
Check the one-vertex tree directly. Its vertex set has size \(1\), its edge set is empty, and its unique vertex has degree \(0\).
For a tree \(T\) of order \(n\ge2\), choose a leaf \(x\) with neighbor \(y\). The graph \(T-x\) is a tree of order \(n-1\).
Use the claim for \(T-x\), not for \(T\). State which vertices and edges it concerns.
Add \(x\) and the edge \(xy\). Work out precisely how the claim changes, and conclude it for \(T\).
This is ordinary induction on the integer \(n\), with the tree lemma supplying the reduction at each step. It is not enough to say that the claim “carries over”: one must check the effect of restoring the leaf. Some properties are unchanged for old vertices; others change at the neighbor \(y\), and the new vertex \(x\) may also contribute to the quantity being counted.
Worked Induction: Counting Edges
Proof. We use induction on \(n\). If \(n=1\), the tree has no edges, so \(|E(T)|=0=1-1\). Now let \(n\ge2\), assume the result for all trees of order \(n-1\), and choose a leaf \(x\) of \(T\). The graph \(T-x\) is a tree of order \(n-1\). By the induction hypothesis it has \((n-1)-1=n-2\) edges. Restoring \(x\) adds exactly one edge, the edge joining \(x\) to its unique neighbor. Therefore \(|E(T)|=(n-2)+1=n-1\), as required. \(\square\)
Worked Example: Following the Edge Count Through Leaf Deletions
Let \(T\) have vertex set \(\{a,b,c,d,e,f\}\) and edge set \(\{ab,ac,ad,de,df\}\). This is a tree: \(a\) is joined to \(b,c,d\), and \(d\) is joined to \(e,f\). Delete leaves in the order \(b,c,e,f,d\). The remaining vertex and edge sets at each stage are:
| Graph | Vertex set | Edge set | Order \(n\) | Size \(m\) |
|---|---|---|---|---|
| \(T\) | \(\{a,b,c,d,e,f\}\) | \(\{ab,ac,ad,de,df\}\) | 6 | 5 |
| \(T-b\) | \(\{a,c,d,e,f\}\) | \(\{ac,ad,de,df\}\) | 5 | 4 |
| \(T-b-c\) | \(\{a,d,e,f\}\) | \(\{ad,de,df\}\) | 4 | 3 |
| \(T-b-c-e\) | \(\{a,d,f\}\) | \(\{ad,df\}\) | 3 | 2 |
| \(T-b-c-e-f\) | \(\{a,d\}\) | \(\{ad\}\) | 2 | 1 |
| \(T-b-c-e-f-d\) | \(\{a\}\) | \(\varnothing\) | 1 | 0 |
At each deletion, the vertex removed has degree \(1\) in the graph at that stage, so the order and size each decrease by one. Checking the formula row by row gives \(6-1=5\), \(5-1=4\), \(4-1=3\), \(3-1=2\), \(2-1=1\), and \(1-1=0\). In particular, reversing the last deletion restores \(d\) and the edge \(ad\), changing the singleton’s edge count from \(0\) to \(1\).
Check: The original edge list contains five edges, and the original vertex set contains six vertices, so the direct count also gives \(m=5=6-1\). The deletion table’s order-4 row is \(\{a,d,e,f\}\) with edges \(\{ad,de,df\}\); it matches the stated deletion sequence.
Worked Induction: At Least Two Leaves
Proof. We induct on the order \(n\), starting at \(n=2\). A connected simple graph on two vertices has the edge joining them; both vertices have degree \(1\), so it has two leaves. Suppose now that \(n\ge3\), and assume the claim for trees of order \(n-1\). Choose a leaf \(x\) of \(T\), let \(y\) be its neighbor, and put \(T'=T-x\). The tree \(T'\) has order \(n-1\ge2\), so by induction it has at least two leaves.
Restoring \(x\) increases the degree of \(y\) by one and does not change the degree of any other vertex of \(T'\). If \(y\) is a leaf of \(T'\), its degree changes from \(1\) to \(2\), so it ceases to be a leaf in \(T\). At least one other leaf of \(T'\) is different from \(y\), since \(T'\) has at least two leaves. That other leaf remains a leaf in \(T\), and the restored vertex \(x\) is itself a leaf. Thus \(T\) has at least two leaves. If \(y\) is not a leaf of \(T'\), all leaves of \(T'\) remain leaves in \(T\), and \(x\) is an additional leaf. In this case \(T\) also has at least two leaves. Both cases establish the induction step. \(\square\)
Worked Example: Restoring a Leaf in a Star
Let \(T\) have vertex set \(\{o,a,b,c,d\}\) and edge set \(\{oa,ob,oc,od\}\). Its degrees are \(\deg(o)=4\) and \(\deg(a)=\deg(b)=\deg(c)=\deg(d)=1\). Thus the four leaves are \(a,b,c,d\).
Delete \(a\). The remaining graph \(T'\) has vertex set \(\{o,b,c,d\}\), edge set \(\{ob,oc,od\}\), and degrees \(\deg_{T'}(o)=3\) and \(\deg_{T'}(b)=\deg_{T'}(c)=\deg_{T'}(d)=1\). It has three leaves. Restoring \(a\) adds the edge \(oa\), increases the degree of \(o\) from \(3\) to \(4\), and gives \(a\) degree \(1\). The three old leaves remain leaves, and the restored vertex is a fourth leaf.
Check: The edge list of \(T\) has four edges and five vertices, consistent with the edge-count theorem, since \(4=5-1\). The direct degree check gives \(4+1+1+1+1=8=2\cdot4\).
Worked Induction: The Parity of Odd Degrees
Proof. We induct on the order of the tree. For the one-vertex tree, the only degree is \(0\), so the number of odd-degree vertices is \(0\), which is even. Let \(T\) be a tree of order \(n\ge2\), assume the result for trees of order \(n-1\), and choose a leaf \(x\) with neighbor \(y\). In \(T-x\), the degree of every vertex other than \(y\) is unchanged. The degree of \(y\) is one less than its degree in \(T\), so its parity changes: if it was odd, it becomes even; if it was even, it becomes odd.
The induction hypothesis says that the number of odd-degree vertices in \(T-x\) is even. If \(y\) is odd in \(T-x\), restoring the edge \(xy\) makes \(y\) even, reducing that count by one, and restoring \(x\), whose degree is \(1\), adds one odd-degree vertex. The total count is unchanged. If \(y\) is even in \(T-x\), restoring \(xy\) makes \(y\) odd, increasing the count by one, and restoring \(x\) increases it by one again. The total count increases by two. In either case the count remains even, proving the claim for \(T\). \(\square\)
Worked Example: Tracking Odd Degrees During Restoration
Let \(T\) have vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,23,24,45\}\). The graph is connected, and its edges form no cycle, so it is a tree. Its degrees are \(\deg(1)=1\), \(\deg(2)=3\), \(\deg(3)=1\), \(\deg(4)=2\), and \(\deg(5)=1\). The odd-degree vertices are \(1,2,3,5\), giving a count of \(4\).
Delete the leaf \(3\) and edge \(23\). In \(T-3\), the vertex set is \(\{1,2,4,5\}\) and the edge set is \(\{12,24,45\}\). Its degrees are \(1,2,2,1\), respectively, so its odd-degree vertices are \(1\) and \(5\), a count of \(2\). When \(3\) is restored, the degree of its neighbor \(2\) changes from \(2\) to \(3\), adding \(2\) to the odd-degree list; the new vertex \(3\) has degree \(1\), adding \(3\) as well. The count changes from \(2\) to \(4\).
Check: The original degree sum is \(1+3+1+2+1=8\), and the four listed edges give \(2|E(T)|=2\cdot4=8\). The direct degree calculation therefore agrees with the edge list, and the odd-degree count is indeed even.
Common Pitfalls and a Practical Check
Do not skip the smallest case. The statement “every tree of order at least \(2\) has at least two leaves” is not true at order \(1\): the singleton has zero leaves. Its proof must start at order \(2\), rather than applying the conclusion to the induction base of order \(1\).
Track the neighbor when restoring the leaf. In the odd-degree proof, it is not enough to count the new leaf \(x\). The degree of its neighbor \(y\) also changes by one, which toggles whether \(y\) has odd degree. Omitting this change can give the wrong count.
Do not confuse connectedness with having no isolated vertices after deletion. The claim that deleting a leaf from a tree cannot leave an isolated old vertex is false for the two-vertex tree. For example, let \(T\) have vertex set \(\{u,v\}\) and edge set \(\{uv\}\). Deleting the leaf \(u\) leaves vertex set \(\{v\}\) and no edges, so \(v\) has degree \(0\). This remaining graph is still connected under the usual definition for a singleton and is a tree. For a tree with more than two vertices, deleting a leaf does not leave an isolated old vertex, as the connectedness argument in the lemma shows.
Before accepting a leaf-induction proof, check four points: the base case matches the exact statement; the chosen vertex is a leaf in the current tree; the reduced graph satisfies the induction hypothesis; and the restoration accounts for the leaf, its edge, and any degree or count that changes at its neighbor.
Check Your Understanding
For each question, identify the base case and state exactly what changes when the leaf is restored.
- In the edge-count induction, how many edges does deleting a leaf remove, and why does that number not depend on the rest of the tree?
- Why must the two-leaf theorem begin at order \(2\), rather than order \(1\)?
- In the proof that a tree has at least two leaves, what happens if the neighbor of the deleted leaf was itself a leaf in the smaller tree?
- For the tree with vertex set \(\{p,q,r,s\}\) and edge set \(\{pq,qr,rs\}\), list the odd-degree vertices and check their number.
- When a leaf \(x\) with neighbor \(y\) is restored, which vertex other than \(x\) can have its degree changed, and by how much?