Why Leaf Deletion Fits Tree Induction
Induction on the number of vertices is especially natural for trees: removing a vertex of degree one removes exactly one edge and leaves a smaller tree. The key is not just to count what disappears. A valid induction step must identify the smaller graph, verify that it still satisfies the theorem’s hypotheses, and then apply the induction hypothesis at the correct order. This tutorial works through that reasoning for two basic conclusions about trees: their edge count and their leaves.
All graphs here are finite and simple. A tree is a connected acyclic graph. The order of a graph \(T\) is \(|V(T)|\), and its size is \(|E(T)|\). A leaf is a vertex of degree one. In particular, a single-vertex tree has no leaves under this definition. A path has no repeated vertices; a longest path in a finite graph means one with the greatest possible number of edges.
Proof. First, take a longest path \(v_0v_1\cdots v_k\) in \(T\). Since \(T\) is connected and has at least two vertices, it has an edge, so \(k\ge1\). The endpoint \(v_0\) has a neighbor \(v_1\). If it had another neighbor \(z\) outside the path, then \(zv_0v_1\cdots v_k\) would be a longer path. If it had another neighbor \(v_i\) on the path with \(i\ge2\), then \(v_0v_1\cdots v_i v_0\) would be a cycle. Both possibilities contradict the choice of path or the fact that \(T\) is acyclic. Thus \(v_0\) has degree one and is a leaf.
Now let \(x\) be a leaf. Deleting a vertex and its incident edge cannot create a cycle, so \(T-x\) is acyclic. To check connectedness, take any two distinct vertices \(u,v\) remaining in \(T-x\). There is a path between them in \(T\), since \(T\) is connected. A leaf cannot be an internal vertex of a path, because an internal vertex has two distinct neighbors along that path. Therefore this path avoids \(x\), and \(u,v\) are still connected in \(T-x\). If only one vertex remains, it is connected by convention. Hence \(T-x\) is a tree. \(\square\)
The lemma has two separate jobs. The longest-path argument supplies a leaf to delete. The second part verifies that the smaller graph remains in the class of trees, which is what makes an induction hypothesis about trees applicable. The case of order one is also included: deleting a leaf from a two-vertex tree leaves a single-vertex tree.
Worked Example: Following a Leaf-Deletion Sequence
Worked Example: Following a Leaf-Deletion Sequence
Let \(T\) have vertex set \(V(T)=\{a,b,c,d,e,f\}\) and edge set \(E(T)=\{ab,ac,ad,be,ef\}\). It is connected: every vertex is joined to \(a\) by a path. It is acyclic: the vertices \(c,d,f\) have degree one, and the remaining edges \(ab,be\) form no cycle. So \(T\) is a tree. Delete the indicated leaf at each stage.
| Graph at this stage | Leaf deleted | Order before deletion | Size before deletion |
|---|---|---|---|
| \(T\) | \(c\) | 6 | 5 |
| \(T-c\) | \(d\) | 5 | 4 |
| \(T-\{c,d\}\) | \(f\) | 4 | 3 |
| \(T-\{c,d,f\}\) | \(e\) | 3 | 2 |
| \(T-\{c,d,f,e\}\) | \(b\) | 2 | 1 |
For example, after deleting \(c\), the remaining edge set is \(\{ab,ad,be,ef\}\), so the order is \(5\) and the size is \(4\). The successive edge sets are \(\{ab,be,ef\}\), \(\{ab,be\}\), \(\{ab\}\), and then the empty set. At each step the deleted vertex has exactly one incident edge in the graph then present.
Check: the original edge list contains \(5\) edges and the vertex list contains \(6\) vertices, so \(|E(T)|=5=6-1=|V(T)|-1\). The deletion sequence reaches one vertex and zero edges, as required for the base case of an edge-count induction.
An Inductive Proof That Trees Have Two Leaves
Proof. We use induction on the order \(n\), with the statement applying to trees of order \(n\ge2\). For \(n=2\), connectedness forces the two vertices to be joined by an edge. Each has degree one, so there are two leaves.
Now let \(n\ge3\), and assume the statement holds for every tree of order \(n-1\). Let \(T\) be a tree of order \(n\). By the lemma, \(T\) has a leaf \(x\), and \(T'=T-x\) is a tree of order \(n-1\). Since \(n-1\ge2\), the induction hypothesis applies to \(T'\): it has at least two leaves. Let \(y\) be the unique neighbor of \(x\) in \(T\). Restoring \(x\) changes the degree of \(y\) by one and changes no other degree in \(T'\). Thus at most one of the leaves of \(T'\), namely \(y\) if \(y\) was a leaf, ceases to be a leaf. At least one leaf of \(T'\) remains a leaf in \(T\); in addition, \(x\) is a leaf in \(T\). Therefore \(T\) has at least two leaves, completing the induction. \(\square\)
Notice exactly where the induction hypothesis enters: it is used on \(T'\), whose order is \(n-1\), and which has already been shown to be a tree. The conclusion is a lower bound of two, not an assertion that all the smaller tree’s leaves survive restoration. One old leaf may be the neighbor \(y\) and gain a second incident edge.
Worked Example: Restoring a Leaf to a Path
Let \(T\) have \(V(T)=\{1,2,3,4\}\) and \(E(T)=\{12,23,34\}\). Delete the leaf \(1\). The smaller graph \(T'\) has \(V(T')=\{2,3,4\}\) and \(E(T')=\{23,34\}\), so it is a tree of order \(3\). Its degrees are \(\deg(2)=1\), \(\deg(3)=2\), and \(\deg(4)=1\); its two leaves are \(2\) and \(4\).
When we restore \(1\), the degree of its neighbor \(2\) increases from \(1\) to \(2\). Thus leaf \(2\) is no longer a leaf, but leaf \(4\) remains a leaf, and the restored vertex \(1\) is a leaf. The original tree has exactly the two leaves \(1\) and \(4\).
Check: in \(T\), the degrees are \(1,2,2,1\), respectively, so exactly vertices \(1\) and \(4\) have degree one. This calculation illustrates the induction step’s “at most one lost leaf” condition: only the neighbor of the restored vertex can change degree.
An Inductive Proof of the Tree Edge Count
Proof. We use induction on \(n\). If \(n=1\), the graph has no edges: a loop is not allowed in a simple graph. Hence \(|E(T)|=0=1-1\).
Let \(n\ge2\), and assume that every tree of order \(n-1\) has exactly \(n-2\) edges. By the lemma, \(T\) has a leaf \(x\). The graph \(T'=T-x\) is a tree, and its order is \(n-1\), so the induction hypothesis gives \(|E(T')|=n-2\). The vertex \(x\) has exactly one incident edge, and deleting it removes precisely that edge. Therefore \(|E(T)|=|E(T')|+1=(n-2)+1=n-1\). The induction hypothesis applies even when \(n=2\): in that case \(T'\) has order one, covered by the base case. \(\square\)
This proof depends on both parts of the leaf-deletion lemma. Knowing that a leaf exists gives the single edge to remove; knowing that \(T-x\) is still a tree allows the induction hypothesis to be used. A vertex deletion that does not preserve connectedness does not provide this justification.
Worked Example: Checking the Edge Count on a Star
Let \(T\) have \(V(T)=\{o,a,b,c\}\) and \(E(T)=\{oa,ob,oc\}\). Each of \(a,b,c\) is a leaf. Delete \(c\), leaving \(T'\) with \(V(T')=\{o,a,b\}\) and \(E(T')=\{oa,ob\}\). This smaller graph is connected and acyclic, hence a tree of order \(3\). Its edge count is \(2=3-1\). Restoring \(c\) adds the single edge \(oc\), so \(|E(T)|=2+1=3\), while \(|V(T)|-1=4-1=3\).
Check: direct counting of the original edge set \(\{oa,ob,oc\}\) gives \(|E(T)|=3\), agreeing with the induction calculation. Its degrees are \(\deg(o)=3\) and \(\deg(a)=\deg(b)=\deg(c)=1\), so the graph is connected and has no cycle, as required for this example to be a tree.
Common Mistake: Deleting an Internal Vertex
Worked Example: Why an Arbitrary Deletion Does Not Work
Let \(T\) have \(V(T)=\{o,a,b,c\}\) and \(E(T)=\{oa,ob,oc\}\), as above. A tempting but invalid move is to delete the internal vertex \(o\). The remaining graph has vertex set \(\{a,b,c\}\) and no edges. It has three components, so it is not a tree. In particular, one cannot apply an induction hypothesis stated for trees to this smaller graph.
The edge count also exposes the faulty step: \(T\) has order \(4\) and size \(3\), but after deleting \(o\) the smaller graph has order \(3\) and size \(0\). It is not true that this smaller graph has \(3-1=2\) edges, because the induction theorem’s tree hypothesis fails. The correction is to delete a leaf, such as \(c\). Then the smaller graph has vertices \(\{o,a,b\}\), edges \(\{oa,ob\}\), order \(3\), and size \(2\); it is a tree, so the induction hypothesis applies. Restoring \(c\) adds one edge and gives size \(2+1=3=4-1\).
Check: deleting \(o\) removes all three edges \(oa,ob,oc\), whereas deleting the leaf \(c\) removes only \(oc\). The latter is exactly the one-edge change used in the edge-count proof.
A Reliable Leaf-Induction Checklist
When writing a proof by deleting a leaf, make the induction logic visible rather than compressing it into “remove a leaf and apply induction.” State the order being inducted on and give the base case. Then, for the induction step, identify a leaf \(x\), name the smaller graph \(T-x\), and verify that it is a tree. State its order, so the reader can see why the induction hypothesis applies. Finally, specify what changes when \(x\) is restored: one edge for the edge-count formula, and the degree of just one vertex for the leaf argument.
These details also prevent errors at the boundary. A one-vertex tree has zero edges but no degree-one leaves. The two-leaf theorem therefore begins at order two, while the edge-count theorem includes order one. Keeping those statements distinct makes both induction proofs valid in every case covered by their hypotheses.
Check Your Understanding
For each question, identify the smaller graph and state why the induction hypothesis does or does not apply.
- In the edge-count proof, what is the order and size of \(T-x\) when \(T\) has order \(n\) and \(x\) is a leaf?
- Why does restoring a deleted leaf cause at most one leaf of the smaller tree to cease being a leaf?
- Why is a one-vertex tree the correct base case for the edge-count theorem but not for the two-leaf theorem?
- In the star example, what goes wrong with applying a tree induction hypothesis after deleting the center?
- Explain why deleting a leaf from a tree cannot disconnect two vertices that remain.