Why Leaf Deletion Matters
A tree is connected and has no cycles. Removing vertices or edges can destroy connectedness, so it is not generally true that deleting part of a tree leaves a tree. A leaf is a special case: because it has only one incident edge, it cannot serve as an intermediate vertex on a path between other vertices. This is the key reason deleting a leaf preserves connectedness.
All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; a path consisting of one vertex has length zero. A graph is connected if every pair of its vertices is joined by a path. A cycle is a closed sequence of at least three edges whose vertices are distinct except that the initial and final vertices coincide. A graph is acyclic if it contains no cycle.
The condition that the tree has at least two vertices matters. It ensures that after deleting a leaf, at least one vertex remains, so the result is still a tree under the definition above. The claim does not require a special convention about whether the empty graph is connected.
What Deletion Can and Cannot Change
Deleting a vertex and its incident edges cannot create a cycle. Any cycle in the resulting graph would use only vertices and edges that were already present, and so would also have been a cycle in the original graph. This inheritance of acyclicity is straightforward; preserving connectedness is the main point to prove.
Proof. Suppose instead that \(H\) contains a cycle. Every vertex and edge of \(H\) is also a vertex or edge of \(G\), because \(H\) was formed only by deletions. Therefore the same sequence of vertices and edges is a cycle in \(G\), contradicting that \(G\) is acyclic. Hence \(H\) is acyclic. \(\square\)
For a leaf \(x\), let \(y\) be its unique neighbor. A path between two vertices other than \(x\) cannot use \(x\) internally: an internal vertex on a path has two distinct neighboring vertices along that path, but \(x\) has only one neighbor in the whole graph. This observation lets us keep paths between the remaining vertices after deleting \(x\).
The Leaf-Deletion Theorem
Proof. Write \(H=G-x\). Since \(G\) has at least two vertices, \(H\) has at least one vertex. By the lemma, \(H\) is acyclic, because it is obtained by deleting a vertex and its incident edge from the acyclic graph \(G\).
It remains to prove that \(H\) is connected. Take any two vertices \(u,v\) of \(H\). If \(u=v\), the length-zero path at \(u\) is a path in \(H\). If \(u\ne v\), connectedness of \(G\) gives a path from \(u\) to \(v\) in \(G\). Neither endpoint is \(x\). The path cannot contain \(x\) internally, because an internal vertex of a path is incident with two distinct path edges, whereas \(x\) has degree \(1\). Thus the whole path uses vertices other than \(x\), and all its edges remain in \(H\). This proves that every pair of vertices of \(H\) is joined by a path in \(H\). So \(H\) is connected and acyclic, hence a tree. \(\square\)
When \(G\) has exactly two vertices, its only possible tree structure is a single edge joining them. Deleting either endpoint leaves a graph with one vertex and no edges. The proof still applies: there are no distinct vertices in the remaining graph that need a connecting path, and the length-zero path handles the sole vertex.
Worked Examples
Worked Example: Deleting an End of a Path
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). The edges join consecutive vertices, so the graph is connected: for any two vertices, the segment of the sequence \(1,2,3,4,5\) between them is a path. It is acyclic: any cycle would have to include a vertex of largest label on that cycle, but among the listed edges that vertex has at most one neighbor with a smaller label and none on the cycle with a larger label. Thus \(G\) is a tree.
Vertex \(1\) has degree \(1\), with unique neighbor \(2\). Deleting \(1\) removes the edge \(12\), so the resulting graph \(H\) has \(V(H)=\{2,3,4,5\}\) and \(E(H)=\{23,34,45\}\). The edges still join consecutive vertices in the list \(2,3,4,5\), so every pair is connected by the intervening segment. The same largest-label argument shows that \(H\) has no cycle. Therefore \(H\) is a tree.
Check: In \(G\), the degrees are \(1,2,2,2,1\), in vertex order \(1,2,3,4,5\). After deletion, the degrees in \(H\) are \(1,2,2,1\), in order \(2,3,4,5\). Only the former neighbor \(2\) loses one incident edge; the retained edges are exactly \(23,34,45\).
Worked Example: Deleting a Leaf from a Branching Tree
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,bc,cd,be,bf,fg\}\). The graph is connected: from \(b\), the vertices \(a,c,d,e,f,g\) are reached along the branches \(ba\), \(bc\), \(bcd\), \(be\), \(bf\), and \(bfg\), respectively. It is acyclic: the graph consists of these paths attached at \(b\), and none of the branches has an edge back to \(b\) or to another branch except through \(b\). A cycle would have to leave \(b\) along a branch and return by a different edge, but no such edge exists. Hence \(G\) is a tree.
Vertex \(d\) is a leaf, and its unique incident edge is \(cd\). After deleting \(d\) and \(cd\), the graph \(H\) has \(V(H)=\{a,b,c,e,f,g\}\) and \(E(H)=\{ab,bc,be,bf,fg\}\). It remains connected: each vertex is still joined to \(b\), by \(ba\), \(bc\), \(be\), \(bf\), or \(bfg\). It is acyclic: its branches from \(b\) are \(ba\), \(bc\), \(be\), \(bf\), and \(bfg\), and no branch has an edge returning to \(b\) or joining another branch away from \(b\). Thus \(H\) is a tree.
Check: The deleted vertex \(d\) had only neighbor \(c\), so no path between two remaining vertices needed to pass through \(d\). In particular, the path from \(c\) to \(g\) is \(c,b,f,g\), and every edge of that path remains after deletion.
Worked Example: The Two-Vertex Boundary Case
Let \(G=(V,E)\), where \(V=\{p,q\}\) and \(E=\{pq\}\). The graph is connected because the only distinct pair \(p,q\) is joined by the path \(p,q\); each vertex is also joined to itself by a length-zero path. There is no cycle, since the graph has only two vertices and a cycle in a simple graph has at least three edges. Therefore \(G\) is a tree, and both vertices have degree \(1\).
Delete the leaf \(p\). The edge \(pq\) is incident with \(p\), so it is deleted as well. The result has \(V(G-p)=\{q\}\) and \(E(G-p)=\varnothing\). This graph is connected: its only pair of vertices to consider is \(q,q\), joined by the length-zero path. It has no cycle, so it is a tree.
Check: The result is not the empty graph: vertex \(q\) remains. This verifies directly that the theorem includes the case \(n=2\).
Common Mistakes and Useful Checks
Do not delete a leaf while keeping its incident edge. For example, in the graph \(V=\{1,2,3\}\), \(E=\{12,23\}\), vertex \(1\) is a leaf. The correct result of deleting it has vertex set \(\{2,3\}\) and edge set \(\{23\}\). A purported result with vertex set \(\{2,3\}\) but edge set \(\{12,23\}\) is not a graph with that vertex set: edge \(12\) uses vertex \(1\), which is no longer present. Deleting a vertex always means deleting all its incident edges.
Do not confuse leaf deletion with deleting an arbitrary vertex. In the star with \(V=\{c,a,b,d\}\) and \(E=\{ca,cb,cd\}\), deleting the center \(c\) leaves three isolated vertices. That graph is not connected, so it is not a tree. The center is not a leaf: its degree is \(3\). The theorem depends on deleting a degree-\(1\) vertex.
One can also track degrees while deleting a leaf \(x\) with unique neighbor \(y\). The degree of \(y\) decreases by one, and the degrees of all other remaining vertices are unchanged, because the only removed edge is \(xy\). This is a useful check on an edge list, but it is not by itself a proof that the remaining graph is a tree: connectedness and acyclicity must still be established.
The structural reason the theorem works is therefore specific and simple. Acyclicity is inherited by every subgraph, while connectedness survives this deletion because a leaf cannot lie internally on a path between the other vertices. Both properties are needed for the conclusion that the result is a tree.
Check Your Understanding
For each question, use the definitions of connectedness, acyclicity and leaf given above.
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), delete leaf \(4\). Give the resulting vertex and edge sets, and explain why the result is a tree.
- Why can a leaf not occur as an internal vertex on a path between two other vertices?
- In the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,da\}\), is \(a\) a leaf? What happens to connectedness if \(a\) is deleted?
- Explain why deleting vertices and edges cannot create a cycle.
- After deleting a leaf from the two-vertex tree, which path verifies connectedness of the remaining graph?