[proofplan] Induction on $n := |V(T)|$. The base case $n = 1$ is immediate: a single-vertex graph has $0 = n - 1$ edges. For the inductive step, given a tree on $n + 1 \ge 2$ vertices, we use [Trees Have Leaves](/theorems/2009) to extract a leaf $x$, and show that $T - x$ is a tree on $n$ vertices by checking separately that it is connected (rerouting any walk through $x$ is unnecessary, because no walk between vertices of $T - x$ ever uses $x$) and acyclic (acyclicity is preserved by vertex deletion). The inductive hypothesis gives $|E(T - x)| = n - 1$, and since deleting a leaf removes exactly one edge (the unique edge incident to $x$), we recover $|E(T)| = n$. [/proofplan] [step:Set up the induction on the vertex count] We prove by induction on $n \ge 1$ the statement \begin{align*} P(n) : \text{every tree } T \text{ with } |V(T)| = n \text{ satisfies } |E(T)| = n - 1. \end{align*} [/step] [step:Verify the base case $n = 1$] Let $T$ be a tree with $|V(T)| = 1$, say $V(T) = \{v\}$. A simple graph has no loops, so the only possible edges of $T$ are among pairs of distinct vertices, of which there are none. Thus $|E(T)| = 0 = 1 - 1 = n - 1$, establishing $P(1)$. [/step] [step:Assume $P(n)$ and work with a tree on $n + 1$ vertices] Fix $n \ge 1$ and assume $P(n)$. Let $T$ be a tree with $|V(T)| = n + 1 \ge 2$. Our goal is to show $|E(T)| = n$. By [Trees Have Leaves](/theorems/2009), the tree $T$ (which has $|V(T)| \ge 2$) has at least two leaves; in particular there exists a leaf $x \in V(T)$, meaning $\deg_T(x) = 1$. Let $y$ denote the unique vertex of $T$ with $xy \in E(T)$. [/step] [step:Verify that $T - x$ is a tree on $n$ vertices] We show $T' := T - x$ is a tree with $|V(T')| = n$. We verify (i) the vertex count, (ii) acyclicity, (iii) connectedness. **(i) Vertex count.** $V(T') = V(T) \setminus \{x\}$, so $|V(T')| = (n + 1) - 1 = n$. **(ii) Acyclicity of $T'$.** Any cycle in $T'$ would be, by the definition of the vertex-deletion operation, a sequence of vertices in $V(T) \setminus \{x\}$ with consecutive pairs in $E(T') \subseteq E(T)$. Such a sequence is also a cycle in $T$. But $T$ is acyclic. Hence $T'$ is acyclic. **(iii) Connectedness of $T'$.** Let $u, v \in V(T')$ with $u \neq v$. Since $T$ is connected and $u, v \in V(T)$, there is a $u$–$v$ walk in $T$, and by [Walk Contains Path](/theorems/2007) there is a $u$–$v$ path \begin{align*} P = u = p_0, p_1, \ldots, p_\ell = v \end{align*} in $T$ with pairwise distinct $p_i$ and each $p_{i-1} p_i \in E(T)$. We claim $x \notin \{p_0, p_1, \ldots, p_\ell\}$. Indeed, $p_0 = u \neq x$ and $p_\ell = v \neq x$ because $u, v \in V(T')$. If $x = p_j$ for some $1 \le j \le \ell - 1$ (an internal vertex), then both $p_{j-1} x = p_{j-1} p_j$ and $x p_{j+1} = p_j p_{j+1}$ are edges of $T$ incident to $x$, exhibiting two distinct neighbours of $x$ in $T$ — namely $p_{j-1}$ and $p_{j+1}$, which are distinct since $P$ is a path. This contradicts $\deg_T(x) = 1$. Hence $x$ does not appear on $P$. Therefore every vertex of $P$ lies in $V(T) \setminus \{x\} = V(T')$, and every edge $p_{i-1} p_i$ lies in $E(T)$ between vertices of $V(T')$, hence in $E(T - x) = E(T')$ (deleting a vertex removes only edges incident to it, and no edge of $P$ is incident to $x$). So $P$ is a $u$–$v$ walk in $T'$. Since $u, v \in V(T')$ were arbitrary, $T'$ is connected. By (ii) and (iii), $T'$ is connected and acyclic, so $T'$ is a tree. Together with (i), $T'$ is a tree on $n$ vertices. [guided] We have three things to check about $T' = T - x$: it has $n$ vertices, it is acyclic, and it is connected. Two of these are quick; the connectivity check is the substantive one and rests crucially on $\deg_T(x) = 1$. **(i) Vertex count.** Deleting one vertex from a set of $n + 1$ vertices leaves $n$ vertices, so $|V(T')| = n$. **(ii) Acyclicity.** A cycle in $T'$ would consist of vertices and edges of $T'$, and every vertex of $T'$ is a vertex of $T$ and every edge of $T'$ is an edge of $T$. So any cycle in $T'$ is *a fortiori* a cycle in $T$. But $T$ is acyclic. Therefore $T'$ is acyclic. (Note: vertex deletion always preserves acyclicity; this argument does not use the leaf hypothesis.) **(iii) Connectedness.** This is where the leaf hypothesis $\deg_T(x) = 1$ is essential. The naive worry is: if $x$ were a "hub" vertex, deleting it would shatter the graph into pieces. We need to show that because $x$ is only a leaf, it cannot lie *between* any pair of other vertices — so removing it does not disconnect anything. Formally, fix distinct $u, v \in V(T')$. Connectedness of $T$ gives a $u$–$v$ walk in $T$. Apply [Walk Contains Path](/theorems/2007) to extract a $u$–$v$ path $P = p_0, p_1, \ldots, p_\ell$ in $T$ with $p_0 = u$, $p_\ell = v$, the $p_i$ pairwise distinct, and each $p_{i-1} p_i \in E(T)$. The key claim is: **$x$ does not appear on $P$**. To see this, inspect where $x$ could possibly sit: - $p_0 = u \neq x$ since $u \in V(T') = V(T) \setminus \{x\}$. - $p_\ell = v \neq x$ for the same reason. - Could $x = p_j$ for some interior index $1 \le j \le \ell - 1$? If so, both edges $p_{j-1} p_j$ and $p_j p_{j+1}$ are incident to $x$ in $T$, so $x$ has at least two neighbours in $T$ — namely $p_{j-1}$ and $p_{j+1}$, and these are distinct because the $p_i$ are pairwise distinct on a path. But $\deg_T(x) = 1$ says $x$ has exactly one neighbour. Contradiction. So $x$ lies nowhere on $P$. This means every vertex of $P$ lies in $V(T')$ and every edge of $P$ lies between vertices of $V(T')$. The vertex-deletion operation $T - x$ removes $x$ from the vertex set and removes exactly those edges incident to $x$; no edge of $P$ is incident to $x$ (otherwise $x$ would be an endpoint of that edge, hence on $P$). So every edge of $P$ survives in $T'$, i.e., $P$ is a $u$–$v$ walk (indeed, a path) in $T'$. Since $u, v \in V(T')$ were arbitrary, $T'$ is connected. Combining (i), (ii), (iii): $T'$ is a tree on $n$ vertices. [/guided] [/step] [step:Apply the inductive hypothesis and count edges] By the inductive hypothesis $P(n)$, since $T'$ is a tree on $n$ vertices, \begin{align*} |E(T')| = n - 1. \end{align*} We relate $|E(T)|$ and $|E(T')|$ directly. The vertex deletion $T' = T - x$ removes, by definition, the vertex $x$ together with all edges of $T$ incident to $x$. The edges of $T$ incident to $x$ are precisely those $e \in E(T)$ with $x$ as an endpoint; since $\deg_T(x) = 1$, there is exactly one such edge, namely $xy$. Hence \begin{align*} E(T') = E(T) \setminus \{xy\}, \qquad |E(T')| = |E(T)| - 1. \end{align*} Solving, \begin{align*} |E(T)| = |E(T')| + 1 = (n - 1) + 1 = n = (n+1) - 1. \end{align*} This establishes $P(n+1)$. By induction, $P(n)$ holds for every $n \ge 1$. So every tree on $n$ vertices has exactly $n - 1$ edges. [/step]