Leaves and Degree Excess
In a tree, vertices of degree two lie along routes between other vertices, while vertices of degree at least three create branches. The number of leaves is constrained by how much branching the tree has: each vertex of degree greater than two contributes an excess above two, and the total excess determines the leaf count exactly. This gives a useful way to find missing degree information and to detect impossible degree counts.
Throughout, graphs are finite and simple. A tree is a connected acyclic graph. A leaf is a vertex of degree one. The result below concerns a nontrivial tree, meaning a tree with at least two vertices. Such a tree has no isolated vertices: connectedness gives every vertex at least one neighbor.
The identity to be derived is \[ \text{number of leaves}=2+\text{total excess degree above two}. \] Vertices of degree two do not appear in the excess sum. A vertex of degree three contributes one, a vertex of degree four contributes two, and so on.
The Degree-Sum Argument
Proof. Count incidences between vertices and edges. Every edge has two distinct endpoints in a simple graph, so contributes one to the degree of each endpoint and therefore contributes two to the total degree sum. Counting the same incidences by vertices gives the sum of the degrees. Hence \(\sum_{v\in V}\deg(v)=2|E|\). \(\square\)
We also use the standard tree edge count: a tree on \(n\) vertices has \(n-1\) edges. This result was established in the earlier material on tree edge counts. Combining it with the Handshake Lemma gives a useful balance around degree two: the sum of all the quantities \(\deg(v)-2\) is \(-2\).
To interpret this equation, separate vertices by degree. Each leaf contributes \(-1\), each degree-two vertex contributes zero, and each vertex of degree at least three contributes a positive amount. Thus the negative contribution from leaves must exceed the positive contribution from branching vertices by exactly two.
Proof. Let \(L\) be the number of degree-one vertices. Since \(T\) is connected and has at least two vertices, every vertex has degree at least one. In the sum \(\sum_{v\in V(T)}(\deg(v)-2)\), each of the \(L\) leaves contributes \(-1\); each degree-two vertex contributes \(0\); and each vertex of degree at least three contributes \(\deg(v)-2\). The sum is therefore \[ -L+\sum_{\substack{v\in V(T)\\\deg(v)\ge3}}(\deg(v)-2). \] The tree edge count and the Handshake Lemma show that this same sum equals \(-2\). Equating the two expressions gives \[ -L+\sum_{\deg(v)\ge3}(\deg(v)-2)=-2, \] so rearranging yields the claimed identity. \(\square\)
The assumption that the tree has at least two vertices matters. A single-vertex tree has degree zero and no degree-one vertices, so it has zero leaves under the definition used here. Substituting it into the displayed identity would give \(0=2\), which is false. The identity is not a statement about that exceptional tree.
Using the Identity
When degree counts are given, multiply the number of vertices of each degree at least three by its excess above two, then add two. The count of degree-two vertices does not affect the answer. It can still be useful for checking the total order and edge count, but it does not change the required number of leaves.
Worked Example: A Tree with Two Degree-Three Vertices and One Degree-Four Vertex
Consider the graph \(T=(V,E)\), where \(V=\{b_0,b_1,b_2,a_1,a_2,a_3,a_4,a_5,a_6,x_1,x_2,x_3,x_4\}\), and \(E=\{b_0x_1,x_1b_1,b_0b_2,b_0x_2,x_2a_1,b_0a_2,b_1x_3,x_3a_3,b_1a_4,b_2x_4,x_4a_5,b_2a_6\}\). The graph is connected: each vertex can be reached from \(b_0\) by following the listed edges. It has 13 vertices and 12 edges, so the standard result that a connected graph on \(n\) vertices with \(n-1\) edges is a tree applies.
Reading the edge list gives \(\deg(b_0)=4\), \(\deg(b_1)=3\), and \(\deg(b_2)=3\). Each \(x_i\) has degree two, and each \(a_i\) has degree one. The excess above two is therefore \[ (4-2)+(3-2)+(3-2)=2+1+1=4. \] The identity gives \(L=2+4=6\) leaves.
Check: The six degree-one vertices are \(a_1,a_2,a_3,a_4,a_5,a_6\), so the direct count is \(L=6\). The degrees sum to \(4+3+3+4\cdot2+6\cdot1=4+3+3+8+6=24\), and twice the number of edges is \(2\cdot12=24\), as required by the Handshake Lemma.
Worked Example: A Tree Whose Degrees Are at Most Two
Let \(T=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56\}\). This is the path \(P_6\), hence a tree. Its endpoints \(1\) and \(6\) each have degree one, and vertices \(2,3,4,5\) each have degree two. There are no vertices of degree at least three, so the total excess is an empty sum, equal to zero. The formula gives \(L=2+0=2\).
Check: Directly, the degree list is \(1,2,2,2,2,1\), so there are exactly two leaves. The degree sum is \(1+2+2+2+2+1=10\), while \(2|E|=2\cdot5=10\). This confirms the degree count used for the tree.
Worked Example: Testing Proposed Degree Counts
Could a tree with eight leaves have one degree-four vertex, three degree-three vertices, and all its other vertices of degree two? The proposed branching vertices contribute \[ (4-2)+3(3-2)=2+3=5 \] to the excess. The leaf-count identity would then require \(L=2+5=7\), not eight. Therefore no such tree exists.
Check: The contradiction can also be seen from the degree sum, without using the leaf-count identity. If there are \(q\) degree-two vertices, the proposed counts give \(n=8+1+3+q=12+q\) vertices and a degree sum of \(8\cdot1+1\cdot4+3\cdot3+q\cdot2=8+4+9+2q=21+2q\). A tree on \(12+q\) vertices has \(11+q\) edges, so its degree sum must be \(2(11+q)=22+2q\). These totals differ by one, confirming that the proposed counts cannot describe a tree.
What the Identity Tells Us
The formula immediately gives a useful special case. If no vertex has degree greater than two, then the excess sum is zero and the tree has exactly two leaves. More generally, each added unit of degree excess requires one additional leaf beyond the basic two. For instance, one degree-five vertex contributes \(5-2=3\), so a tree with that vertex and no other branching vertices must have five leaves.
Conversely, if the number of leaves and all but some of the branching degrees are known, the same equation can constrain the missing counts. For example, if a tree has seven leaves and its only vertices of degree at least three are degree-four and degree-three vertices, with counts \(r\) and \(s\), respectively, then \[ 7=2+2r+s,\qquad\text{so}\qquad 2r+s=5. \] This is a necessary condition on the counts. It does not by itself establish that every solution is realized by a tree; existence must be checked separately.
The identity is useful because it turns a global structural question into arithmetic on degrees. It is especially effective when a problem specifies branching degrees but omits the number of leaves, or asks whether a proposed list of degrees could belong to a tree. It also makes clear why adding degree-two vertices along edges does not affect the leaf count: such vertices contribute zero to the excess sum.
Common Pitfall
A frequent error is to equate the number of leaves with the total excess degree, omitting the additional two. In the first worked example, the excess is \(4\), so that incorrect calculation would give \(L=4\). But the actual degree-one vertices are \(a_1,\ldots,a_6\), giving \(L=6\). The correction is the constant term in the identity: the total degree balance is \(-2\), not \(0\), because a tree has \(n-1\) edges. Thus the right calculation is \(L=2+4=6\).
Another point to keep in view is the hypothesis \(n\ge2\). A one-vertex tree is a tree, but it has degree zero rather than degree one. Do not apply the leaf-count identity to it.
Check Your Understanding
Use the leaf-count identity where it applies, and show the degree counts that support each answer.
- A nontrivial tree has four vertices of degree three and one vertex of degree five. How many leaves must it have?
- A nontrivial tree has five leaves and two vertices of degree four. If all other vertices have degree at most two, is this possible? Explain.
- A nontrivial tree has exactly one vertex of degree at least three, and that vertex has degree six. How many leaves does the tree have?
- Explain why vertices of degree two do not change the leaf-count identity.
- Why can the identity not be applied to a single-vertex tree under the definition of leaf used here?