The Leaf-Removal Test
A tree can be recognized by repeatedly removing leaves: each removal peels away a vertex attached to the rest of the graph by just one edge. The stopping rule matters. We remove one leaf at a time, and accept only if the process reaches exactly one vertex. Reaching an empty graph is not acceptance, and stopping with two or more vertices is not acceptance.
All graphs in this tutorial are finite and simple. The degree of a vertex is the number of its neighbors in the graph currently being considered. A leaf is a vertex of degree one. Deleting a vertex means removing it and all its incident edges. A tree is a connected acyclic graph; a single vertex is a tree, while the empty graph is not.
Different choices can produce different deletion orders, so it is useful to know that the test does not depend on making a special choice: every possible sequence accepts when the graph is a tree, and no sequence accepts when it is not a tree. The proof establishes this guarantee.
Worked Traces
Worked Example: Peeling a Tree
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,cd,de\}\). This is the path \(a,b,c,d,e\). At each step, choose one current leaf and delete it.
| Current vertices | Current edges | Current leaves | Choice and result |
|---|---|---|---|
| \(\{a,b,c,d,e\}\) | \(\{ab,bc,cd,de\}\) | \(a,e\) | Delete \(a\); the remaining path is \(b,c,d,e\). |
| \(\{b,c,d,e\}\) | \(\{bc,cd,de\}\) | \(b,e\) | Delete \(b\); the remaining path is \(c,d,e\). |
| \(\{c,d,e\}\) | \(\{cd,de\}\) | \(c,e\) | Delete \(c\); the remaining edge is \(de\). |
| \(\{d,e\}\) | \(\{de\}\) | \(d,e\) | Delete \(d\); the remaining graph has vertex \(e\). |
The process accepts after four deletions, leaving the single vertex \(e\). At each step the chosen vertex has degree exactly one in the graph shown in that row. The reverse order reconstructs the path by attaching \(d\) to \(e\), then \(c\) to \(d\), then \(b\) to \(c\), then \(a\) to \(b\), each time using one edge.
Check: the starting graph has five vertices and four edges, and the four deletions each remove one edge. The final graph has one vertex and no edges, as expected. The original graph is connected and has no cycle: its edges only join consecutive vertices in the listed path.
Worked Example: A Disconnected Forest
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,de\}\). Its components are the path \(a,b,c\) and the edge \(de\). One legal sequence is to delete \(a\), then \(c\), then \(d\).
| Current vertices | Current edges | Current leaves | Choice and result |
|---|---|---|---|
| \(\{a,b,c,d,e\}\) | \(\{ab,bc,de\}\) | \(a,c,d,e\) | Delete \(a\); the remaining edges are \(bc,de\). |
| \(\{b,c,d,e\}\) | \(\{bc,de\}\) | \(b,c,d,e\) | Delete \(c\); the remaining edge is \(de\), and \(b\) is isolated. |
| \(\{b,d,e\}\) | \(\{de\}\) | \(d,e\) | Delete \(d\); the remaining vertices \(b,e\) are both isolated. |
Now the graph has two vertices and no degree-one vertex, so the process rejects. The original graph is a forest, but not a tree because it is disconnected. In particular, peeling leaves does not join separate components: a deletion can remove a vertex from a component, but when that vertex has degree one, its remaining neighbor keeps that component nonempty.
Check: the original graph has three edges. The deletions of \(a\), \(c\), and \(d\) remove \(ab\), \(bc\), and \(de\), respectively, leaving no edges. They do not remove the last vertex of either original component, so two isolated vertices remain.
Worked Example: A Cycle with a Pendant Path
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,34,45\}\). The vertices \(1,2,3\) form a triangle, with the path \(3,4,5\) attached. Initially, \(5\) is the only degree-one vertex, so delete it. The remaining graph has vertices \(\{1,2,3,4\}\) and edges \(\{12,23,31,34\}\); its only leaf is \(4\), so delete \(4\).
The residual graph has vertices \(\{1,2,3\}\) and edges \(\{12,23,31\}\). Each vertex has degree two, so there is no legal deletion. The test rejects. The triangle remains because none of its vertices can be the first triangle vertex deleted: while its three edges remain, each such vertex has at least its two triangle neighbors.
Check: the original degrees are \(2,2,3,2,1\), in vertex order \(1,2,3,4,5\), so \(5\) is the only initial leaf. After removing \(5\), vertex \(4\) has degree one and the triangle vertices have degrees \(2,2,3\). Removing \(4\) leaves three vertices of degree two, confirming the stopping point.
Why the Test Works
Proof. First suppose \(G\) is a tree. If it has one vertex, it is accepted immediately. If it has at least two vertices, it has a leaf: choose a path with as many vertices as possible, which exists because the graph is finite. An endpoint 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, since that edge together with the intervening section of the path would form a cycle. Thus the endpoint has degree one.
Deleting a leaf from a tree with at least two vertices leaves a tree. The remaining graph is acyclic because deleting vertices cannot create a cycle. It is connected because a path between two remaining vertices cannot use the deleted degree-one vertex as an internal vertex: an internal vertex on a path has two incident path edges. The remaining graph is nonempty, including when the original tree had two vertices. Therefore, after any legal leaf choice, the residual graph is again a tree. Repeating this argument decreases the number of vertices by one each time and must eventually reach a single vertex, where the process accepts.
Conversely, suppose the process accepts. If \(G\) started with one vertex, it is a tree. Otherwise, let \(v_1,\ldots,v_{n-1}\) be the vertices deleted in order, and let \(r\) be the final vertex. At the moment \(v_i\) was deleted, it had exactly one neighbor among the vertices still present, namely those in \(\{v_{i+1},\ldots,v_{n-1},r\}\). Rebuild the graph in reverse order, starting with \(r\) and adding \(v_{n-1},\ldots,v_1\). When \(v_i\) is added, its neighbors already rebuilt are exactly its neighbors among the vertices that were still present when it was deleted. Thus it is attached to the rebuilt graph by exactly one edge.
Starting from one vertex, each such addition preserves connectedness: the new vertex is joined to the existing graph. It also preserves acyclicity: a cycle using the new vertex would require that vertex to have at least two incident edges, but it has only one. Hence the rebuilt graph, which is \(G\), is connected and acyclic, so it is a tree. This proves both directions. The argument also shows why no particular leaf choices are needed for a tree. \(\square\)
Reading a Rejection
The theorem explains the two common reasons a process stops without acceptance. A graph containing a cycle cannot lose all its vertices by leaf deletion: the vertices of any cycle remain, because as long as the cycle remains, each of them has its two cycle edges. A disconnected graph also cannot be reduced to one vertex by these deletions. Removing a degree-one vertex leaves its neighbor behind in that same component, so each nonempty component remains nonempty. These facts account for the cyclic and forest traces above.
For a graph with both cyclic and acyclic parts, leaf removal may strip away some vertices before stopping. The remaining graph can include a cycle together with vertices attached to it; the process only certifies rejection, not that every remaining vertex lies on a cycle. For example, the triangle trace stopped with exactly the triangle because its attached path was completely peeled away.
Common Pitfalls
Deleting all current leaves at once can give the wrong answer. Take \(G\) with \(V=\{x,y\}\) and \(E=\{xy\}\). Both vertices have degree one. Simultaneously deleting every current leaf leaves the empty graph, which would wrongly suggest rejection. Under the specified sequential process, delete \(x\) first; \(y\) remains as a single vertex, so the test accepts. This graph is a tree.
Do not delete isolated vertices as if they were leaves. A leaf has degree exactly one, not degree zero. For example, let \(V=\{a,b,c\}\) and \(E=\{ab\}\). This graph is disconnected. If a different procedure deletes every vertex of degree at most one, it could delete \(a,b,c\) and reach the empty graph. That is not the leaf-removal test, and accepting or interpreting that empty result as a tree would be incorrect. With the stated rule, delete one of \(a,b\), then the other becomes isolated; \(c\) was already isolated. The process stops with two isolated vertices and correctly rejects.
Finally, reaching a graph with no leaves is not by itself a verdict. One vertex is acceptance; two or more vertices with no degree-one vertex is rejection. The empty graph is also rejection. Keeping these stopping cases separate is essential, especially when a graph has isolated vertices or several components.
Using the Test
The test gives a simple certificate when it accepts: it supplies an order in which the vertices can be removed as leaves until one vertex remains. Reversing that order shows how to build the graph from a single vertex by repeatedly attaching one new vertex with one edge. If it rejects, the residual graph has more than one vertex and no leaf, or the starting graph was empty. The proof shows that such a rejection rules out a tree; it does not require the residual graph itself to be connected or to consist only of cycles.
Check Your Understanding
For each question, use the rule that a legal deletion removes exactly one current degree-one vertex.
- Apply the test to the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Give a deletion order and the final vertex.
- Apply the test to the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\). List the residual graph at which the process stops.
- Explain why a degree-one deletion cannot remove the last vertex of a connected component.
- Why does the proof that a tree is accepted need to know that deleting a leaf preserves connectedness as well as acyclicity?
- Give an example showing why reaching the empty graph must not count as acceptance under this test.