Leaves at the Ends of a Longest Path
A tree may have a complicated arrangement of branches, but its longest paths have a simple feature: both endpoints are leaves. This gives a direct way to prove that a tree with at least two vertices has at least two leaves. The argument uses two properties of a tree: it is connected, so there is a path between vertices, and it is acyclic, so an extra edge back to an earlier point on a path would create a cycle.
Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. Its length is the number of edges in the sequence. A tree is a connected, acyclic graph. The degree \(\deg(v)\) of a vertex \(v\) is the number of its neighbors, and a leaf is a vertex of degree one.
Since the graph is finite, it has only finitely many paths, so a path of greatest length exists whenever there is at least one path. In a tree with at least two vertices, connectedness ensures that there is an edge and hence a path of positive length. In particular, a longest path in such a tree has two distinct endpoints.
Why the Endpoints Must Be Leaves
Proof. Let \(T\) be a finite tree with at least two vertices, and write a longest path as \(v_0,v_1,\ldots,v_k\), where \(k\geq 1\). Consider the endpoint \(v_0\). It is adjacent to \(v_1\), so \(\deg(v_0)\geq 1\). Suppose it has another neighbor \(w\neq v_1\).
If \(w\) is one of the path's vertices, then \(w=v_i\) for some \(i\geq 2\), since the graph is simple and \(w\neq v_1\). The edges along \(v_0,v_1,\ldots,v_i\), together with the edge \(v_iv_0\), form a cycle of length \(i+1\geq 3\). This contradicts that \(T\) is acyclic.
If \(w\) is not on the path, then \(w,v_0,v_1,\ldots,v_k\) is a path: its vertices are distinct, and every consecutive pair is adjacent. Its length is \(k+1\), greater than the length \(k\) of the chosen longest path. This is a contradiction. Thus \(v_0\) has no neighbor other than \(v_1\), and \(\deg(v_0)=1\).
The same argument applies to the other endpoint \(v_k\): it has at least the neighbor \(v_{k-1}\); any additional neighbor on the path would create a cycle, and any additional neighbor off the path would extend it. Therefore \(\deg(v_k)=1\) as well. \(\square\)
Proof. Choose a longest path in the tree. Its length is at least one, so its two endpoints are distinct. By the Lemma, each endpoint has degree one. They are therefore two distinct leaves. \(\square\)
The proof also explains exactly why the path must be longest. An endpoint cannot have an unused neighbor outside the path, because that would extend the path. It cannot have another neighbor already on the path, because that would create a cycle. The endpoint's one neighbor along the path is therefore its only neighbor.
Worked Examples
Worked Example: A Path-Shaped Tree
Let \(T\) have vertex set \(V(T)=\{1,2,3,4,5\}\) and edge set \(E(T)=\{12,23,34,45\}\). These edges join the vertices consecutively, so the graph is connected and contains no cycle; it is a tree.
The path \(1,2,3,4,5\) has four edges. It uses all five vertices, so no path in this graph can have more than four edges: a path cannot repeat vertices, and there are only five vertices. Thus this path is longest. The degrees, calculated by counting incident edges, are \(\deg(1)=1\), \(\deg(2)=2\), \(\deg(3)=2\), \(\deg(4)=2\), and \(\deg(5)=1\).
Check: The endpoints are \(1\) and \(5\), and each has degree one. The only vertices of degree one are \(1\) and \(5\), in agreement with the theorem.
Worked Example: A Star
Let \(T\) have vertex set \(V(T)=\{c,a,b,d,e\}\) and edge set \(E(T)=\{ca,cb,cd,ce\}\). The center \(c\) is joined to each of the other vertices, so the graph is connected. Every edge has \(c\) as an endpoint, and no edge joins two other vertices; hence there is no cycle. This graph is a tree.
A path can use at most two of \(a,b,d,e\). Each of these vertices is adjacent only to \(c\), so if a path passes through one of them, that vertex can only be at an endpoint. A path using two leaves, such as \(a,c,b\), has length two. This length is attainable, and a path cannot use more than two leaves, so the longest-path length is exactly two.
Counting incident edges gives \(\deg(c)=4\) and \(\deg(a)=\deg(b)=\deg(d)=\deg(e)=1\). For the particular longest path \(a,c,b\), the endpoints \(a\) and \(b\) are leaves. Other longest paths, such as \(d,c,e\), have different endpoints, also leaves.
Check: The calculated path length is \(1+1=2\), one edge from \(a\) to \(c\) and one from \(c\) to \(b\). No longer path is possible because each leaf has only one incident edge and a path cannot repeat the center.
Worked Example: A Tree with Branches of Different Lengths
Let \(T\) have vertex set \(V(T)=\{1,2,3,4,5,6,7\}\) and edge set \(E(T)=\{12,23,24,45,46,67\}\). The graph is connected: from \(2\), the vertices \(1\) and \(3\) are reached directly, \(4\) is reached directly, \(5\) and \(6\) are reached through \(4\), and \(7\) is reached through \(4,6\). There is no cycle: the branches from \(2\) go to \(1\), to \(3\), or through \(4\) to \(5\) and to \(6,7\), with no edges joining these branches back together. Thus \(T\) is a tree.
The degrees found by listing each vertex's neighbors are \(\deg(1)=1\), \(\deg(2)=3\), \(\deg(3)=1\), \(\deg(4)=3\), \(\deg(5)=1\), \(\deg(6)=2\), and \(\deg(7)=1\). For example, the neighbors of \(2\) are \(1,3,4\), and the neighbors of \(4\) are \(2,5,6\).
The path \(1,2,4,6,7\) has four edges. It is longest: on the \(2\)-side, a path can extend from \(2\) to at most one of \(1\) and \(3\), adding at most one edge before reaching \(2\); on the other side, it can continue from \(4\) along the longer branch \(4,6,7\), adding two edges after reaching \(4\). The segment from \(2\) to \(4\) contributes one more edge. Thus no path can have more than \(1+1+2=4\) edges. The path \(3,2,4,6,7\) also has four edges.
Check: The endpoints of \(1,2,4,6,7\) are \(1\) and \(7\), and the degree list gives \(\deg(1)=1\) and \(\deg(7)=1\). For the other displayed longest path, \(\deg(3)=1\) and \(\deg(7)=1\). Both checks agree with the Lemma.
What the Argument Does—and Does Not—Say
The theorem guarantees at least two leaves; it does not say that every vertex on a longest path is a leaf. In the branched example, vertices \(2\) and \(4\) lie on a longest path and each has degree three. The claim concerns the two endpoints only.
Nor does the argument apply to an arbitrary path. For instance, let \(G\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,13,14\}\). The path \(1,2\) has endpoint \(1\), but \(\deg(1)=3\), so this endpoint is not a leaf. That path is not longest: the path \(2,1,3\) has length two, while \(1,2\) has length one. In the longest path \(2,1,3\), the endpoints \(2\) and \(3\) both have degree one.
Common pitfall: It is incorrect to reason that an endpoint has only one neighbor just because it is an endpoint of the path. The path condition only rules out additional neighbors that lie on that path. The key extra condition is that the path is longest: an additional neighbor outside the path would make a longer path. The proof must also use acyclicity to rule out an additional neighbor on the path.
The assumption of at least two vertices matters. A one-vertex tree is connected and acyclic, but its only vertex has degree zero, so it has no leaf under the degree-one definition. When there are at least two vertices, a longest path has positive length and distinct endpoints, exactly as required by the proof.
This result is useful because it identifies leaves without needing to inspect every vertex's role in the whole tree: select a longest path, and its endpoints are guaranteed leaves. The guarantee holds for every choice of longest path, even when several paths tie for the greatest length.
Check Your Understanding
Use the endpoint argument, and distinguish carefully between a longest path and an arbitrary path.
- Let \(T\) have vertices \(\{a,b,c,d\}\) and edges \(\{ab,bc,cd\}\). Find a longest path and identify its endpoints and their degrees.
- Explain why an additional neighbor of an endpoint that lies on the chosen longest path would contradict acyclicity.
- Explain why an additional neighbor outside the chosen longest path would contradict the path's maximal length.
- In the tree with vertices \(\{1,2,3,4,5\}\) and edges \(\{12,23,24,45\}\), give a longest path and check the degrees of its endpoints.
- Why does the theorem require at least two vertices if a leaf is defined to have degree one?