Question

Prove, by induction on $n$, that for all $n \ge 1$, every tree on $n$ vertices has $n-1$ edges.

Use the fact that every tree with more than one vertex has a leaf (a vertex connected to only one edge).

---

Inductive Proof

We will prove the proposition $P(n)$: "Every tree on $n$ vertices has $n-1$ edges" for all integers $n \ge 1$.

1. Base Case: $P(1)$

   We test the proposition for $n=1$. A tree with $1$ vertex consists of a single node and has no edges. The formula states the number of edges should be $n-1 = 1-1 = 0$. Since a 1-vertex tree has 0 edges, the proposition $P(1)$ is true.

2. Inductive Hypothesis

   We assume that the proposition $P(k)$ is true for some arbitrary integer $k \ge 1$. That is, we assume that every tree with $k$ vertices has $k-1$ edges.

3. Inductive Step: Proving $P(k+1)$

   Our goal is to prove that any tree with $k+1$ vertices must have $(k+1)-1 = k$ edges.

   Let $T$ be an arbitrary tree with $k+1$ vertices. Since $k \ge 1$, the number of vertices $k+1 \ge 2$. According to the provided hint, any tree with more than one vertex must have a leaf.

   Let's choose a leaf vertex from $T$ and call it $v$. By definition, a leaf is connected to exactly one edge. Let's call this edge $e$.

   Now, let's construct a new graph, $T'$, by removing the vertex $v$ and the edge $e$ from the tree $T$.

   • $T'$ has $(k+1) - 1 = k$ vertices.
   • $T'$ has one fewer edge than $T$.
   • Removing a leaf and its single connecting edge from a tree cannot create a cycle or disconnect the graph. Therefore, $T'$ is also a tree.

   Since $T'$ is a tree with $k$ vertices, we can apply our Inductive Hypothesis to it. The hypothesis states that $T'$ must have $k-1$ edges.

   The original tree $T$ was formed by adding the vertex $v$ and the edge $e$ to $T'$. Thus, the number of edges in $T$ is the number of edges in $T'$ plus one.

   Number of edges in $T = (\text{Edges in } T') + 1 = (k-1) + 1 = k$.

   This is exactly what we needed to show: a tree with $k+1$ vertices has $k$ edges. Therefore, the proposition $P(k+1)$ is true.

4. Conclusion

   Since we have shown that the base case $P(1)$ is true and that the truth of $P(k)$ implies the truth of $P(k+1)$, we conclude by the Principle of Mathematical Induction that every tree on $n$ vertices has $n-1$ edges for all $n \ge 1$.

Changelog

9/7/25, 2:51 AM

View All Changelog

• 87c17-web-deploy(Auto): Update base URL for web-pages branchon 9/7/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)