Two Small Graphs That Need Different Conventions
Many theorems about trees are stated for all trees, and many formulas involve the number of vertices, edges, components, or leaves. At the smallest orders, the definitions matter: the graph with one vertex has no edges but is connected, while the graph with no vertices has neither vertices nor edges. Treating these graphs as interchangeable can make a correct formula appear to fail or make a leaf statement appear to hold when it does not.
Throughout, graphs are finite and simple. A graph is acyclic if it contains no cycle. A graph is connected here if it is nonempty and every pair of its vertices is joined by a path. A component is a maximal connected subgraph. A leaf means a vertex of degree one; degree-zero vertices are not leaves under this convention.
Under these conventions, the graph with one vertex and no edges is a tree: it is nonempty, has no cycles, and its only vertex is connected to itself by the path of length zero. The empty graph is a forest, since it has no cycles, but it is not a tree because it is not nonempty. Some authors use a convention that regards the empty graph as connected, or even as a tree. If that convention is used, statements about trees must make a corresponding exception where needed; in particular, the formula \(|E|=|V|-1\) cannot hold for the empty graph.
Edge Counts at Orders Zero and One
For a tree with \(n\) vertices, the usual edge-count formula is \(|E|=n-1\). Its smallest permitted order is \(n=1\), not \(n=0\). The one-vertex case fits the formula: it has zero edges, and \(1-1=0\). By contrast, the empty graph has \(n=0\) and \(|E|=0\), so \(|E|=n-1\) would assert \(0=-1\), which is false.
Proof. We use induction on the order \(n=|V(T)|\), with the standing assumption that \(T\) is a tree and hence \(n\ge1\). If \(n=1\), then there can be no edge in a simple graph on one vertex, so \(|E(T)|=0=1-1\).
Now let \(n\ge2\), and assume the formula holds for every tree of order \(n-1\). A longest path in \(T\) has an endpoint of degree one: the endpoint cannot have a neighbor outside the path, since that would extend the path, or another neighbor on the path, since that would create a cycle. Let \(x\) be such an endpoint. By the earlier result that deleting a leaf preserves tree structure, \(T-x\) is a tree of order \(n-1\). The induction hypothesis gives \(|E(T-x)|=(n-1)-1=n-2\). Restoring \(x\) restores exactly its one incident edge, so \(|E(T)|=(n-2)+1=n-1\). This proves the formula for every tree under the stated convention. \(\square\)
The forest formula makes the role of components explicit. Write \(c(F)\) for the number of components of a forest \(F\); in particular, the empty graph has zero components. Each nonempty component of a forest is a tree. Summing the tree edge counts over all components gives the formula below, including for the empty forest.
Proof. If \(F\) has \(c(F)>0\) components, let their orders be \(n_1,\ldots,n_{c(F)}\). Each component is a tree and therefore has \(n_i-1\) edges. Components have disjoint vertex and edge sets, so \(|E(F)|=\sum_{i=1}^{c(F)}(n_i-1)=\sum_{i=1}^{c(F)}n_i-c(F)=|V(F)|-c(F)\). If \(F\) is empty, then \(|V(F)|=0\), \(|E(F)|=0\), and \(c(F)=0\), so the formula reads \(0=0-0\) and holds as well. \(\square\)
Worked Example: The One-Vertex Tree
Let \(G\) have \(V(G)=\{a\}\) and \(E(G)=\varnothing\). It has order \(n=|V(G)|=1\) and size \(m=|E(G)|=0\). There is no cycle because a simple graph has no loop and there is no edge. The graph is connected under the stated definition: the only pair of vertices to consider is \(a,a\), and the length-zero path joins \(a\) to itself. Thus \(G\) is a tree.
The tree edge-count formula gives \(n-1=1-1=0\), which agrees with \(m=0\). The degree of \(a\) is \(\deg(a)=0\), so \(a\) is not a leaf under the degree-one convention. This example shows that the phrase “every tree has a leaf” needs an order condition: it is true for trees of order at least two, but not for this tree.
Check: The handshake lemma gives \(\sum_{v\in V(G)}\deg(v)=0\), while \(2m=2\cdot0=0\), so the degree sum also agrees with the edge list.
Worked Example: The Empty Graph
Let \(H\) have \(V(H)=\varnothing\) and \(E(H)=\varnothing\). Its order is \(n=0\) and its size is \(m=0\). It is acyclic because it has no vertices and therefore no cycles. Under the convention in this tutorial it is a forest, but not a tree: it fails the nonempty requirement in the definition of a tree.
There are no components, so \(c(H)=0\). Substitution into the forest formula gives \(n-c(H)=0-0=0=m\). Substitution into the tree formula would instead give \(n-1=0-1=-1\), which is not \(m=0\). The failed tree formula is not a counterexample to the proposition: \(H\) is not a tree.
Check: The empty graph has no vertices whose degrees could contribute to the degree sum, so the sum is \(0\). Its edge count gives \(2m=2\cdot0=0\), in agreement. The empty graph has no leaves because it has no vertices.
Leaves and the Smallest Tree
For trees of order at least two, the endpoints of a longest path are distinct leaves. The order restriction is essential: when the tree consists of a single vertex, a longest path has length zero and has only one endpoint vertex, whose degree is zero. It is not a leaf as defined here.
Proof. The one-vertex assertion follows because its only vertex has degree zero. Now let \(T\) be a tree with at least two vertices, and choose a path of maximum length. Its length is at least one because \(T\) is connected and has two or more vertices. Let \(x\) and \(y\) be its distinct endpoints. If \(x\) had a neighbor outside the path, that neighbor could be added to extend the path, contrary to maximal length. If \(x\) had a neighbor on the path other than its next vertex, that edge together with the portion of the path between the two vertices would form a cycle, contrary to acyclicity. Thus \(x\) has exactly one neighbor and is a leaf. The same reasoning applies to \(y\), so the two distinct endpoints are leaves. \(\square\)
A related degree identity makes the exceptional order visible. If \(L(T)\) is the number of leaves of a tree \(T\) with \(n\ge2\), then
To obtain the identity, the tree edge count gives \(n-1\) edges, and the handshake lemma gives \(\sum_{v\in V(T)}\deg(v)=2(n-1)\). Hence \(\sum_{v\in V(T)}(\deg(v)-2)=-2\). For \(n\ge2\), connectedness rules out degree-zero vertices. Degree-one vertices contribute \(-1\) each, degree-two vertices contribute \(0\), and vertices of degree at least three contribute \(\deg(v)-2\). Rearranging gives the displayed formula. It is not stated for \(n=1\): that graph has one degree-zero vertex, so the argument separating vertices of degrees one, two, and at least three does not apply.
Worked Example: A Tree with an Isolated-Looking Endpoint
Let \(T\) have \(V(T)=\{a,b,c\}\) and \(E(T)=\{ab,bc\}\). The graph is a path: it is connected, and with only these two edges it has no cycle. Its order is \(n=3\), and its size is \(m=2\). The tree edge-count check is \(n-1=3-1=2=m\).
The degrees are \(\deg(a)=1\), \(\deg(b)=2\), and \(\deg(c)=1\), so \(a\) and \(c\) are leaves and \(L(T)=2\). In the degree identity, there are no vertices of degree at least three, so the sum is \(0\); the right-hand side is \(2+0=2\), matching the leaf count. The handshake check is \(\deg(a)+\deg(b)+\deg(c)=1+2+1=4\), and \(2m=2\cdot2=4\).
Check: The two leaves are the endpoints of the path \(a,b,c\). The middle vertex has degree two, so it contributes zero to the degree identity; no degree-zero vertex is being counted as a leaf.
Common Mistakes and Why the Conventions Matter
Wrong calculation: “Every tree has at least two leaves, so the one-vertex tree has two leaves.” This applies the longest-path conclusion without its hypothesis \(n\ge2\). In the one-vertex graph \(V=\{a\}\), \(E=\varnothing\), the actual degree is \(\deg(a)=0\), not \(1\), so it has no leaves under the convention used here. The correction is to state the result as “every tree with at least two vertices has at least two leaves.”
Wrong calculation: “The empty graph is a tree, and therefore it has \(n-1=-1\) edges.” The edge count cannot be negative. Under the convention used here, the empty graph is a forest, not a tree; its forest count is \(m=n-c=0-0=0\). If another convention calls it a tree, then the tree edge-count statement must explicitly exclude that graph or be adjusted to accommodate the convention.
These distinctions matter whenever a statement includes an unqualified phrase such as “for every tree,” “every tree has a leaf,” or “a forest with \(c\) components has \(n-c\) edges.” State whether the empty graph is allowed, say whether a leaf means degree exactly one, and specify any lower bound on the order. With those hypotheses visible, the one-vertex and empty cases fit consistently into the surrounding theory.
Check Your Understanding
Use the definitions in this tutorial, and state the convention or order assumption relevant to each answer.
- For the graph \(V=\{x\}\), \(E=\varnothing\), give its order, size, degree, and number of leaves. Is it a tree?
- For the empty graph, give its order, size, and number of components. Verify the forest edge-count formula.
- Why does the expression \(n-1\) fail to give the edge count of the empty graph, and why does that not contradict the tree edge-count proposition here?
- State the correct order condition for the claim that every tree has at least two leaves.
- For a tree with \(n\ge2\), explain why its degree-zero vertices do not need a separate term in the leaf-count identity.