Tree Properties and Proof of Edge Count

Purpose

A tree is a connected graph with no cycles. This note proves the edge count of a tree by induction and records the two-out-of-three characterization that makes trees easy to recognize.

Edge Count

Claim: every tree with $n$ vertices has $n-1$ edges.

A tree on $6$ vertices has $5$ edges, and removing any leaf leaves a tree on $5$ vertices with $4$ edges. The proof below runs that deletion in reverse:

flowchart TD
    a((a)) --- b((b))
    a --- c((c))
    b --- d((d))
    b --- e((e))
    c --- f((f))

Proof: by induction on $n$.

Base case: $n=1$. A tree with 1 vertex has 0 edges.

Inductive hypothesis: suppose every tree with $n-1$ vertices has $n-2$ edges.

Inductive step: let $T$ be a tree with $n\ge 2$ vertices. Since $T$ is acyclic, it has a vertex of degree at most 1 (proved in graph fundamentals), and since $T$ is connected with at least 2 vertices, that vertex has degree exactly 1. Remove it and its edge to get a graph $T^{\prime }$ with $n-1$ vertices. $T^{\prime }$ is still connected (the removed vertex was a leaf) and still acyclic, so it is a tree, and by the inductive hypothesis it has $n-2$ edges. Adding the vertex and its edge back gives $n-1$ edges. $■$

Leaf Bound

Trees need enough leaves to support their branching points.

Claim: if $T$ is a tree, then the number of leaves of $T$ is at least the number of vertices of degree at least $3$.

Proof: by induction on the number of vertices.

Base case: a one-vertex tree has no leaves and no vertices of degree at least $3$.

Inductive step: let $T$ be a tree on $n+1$ vertices, and remove a leaf $\ell$ and its incident edge. The remaining graph $T^{\prime }$ is still a tree. By the inductive hypothesis,

$$\#\text{leaves}(T^{\prime })\ge \#\{v\in T^{\prime }:deg(v)\ge 3\}.$$

Let $p$ be the former neighbor of $\ell$.

• If $de{g}_{T^{\prime }}(p)=1$, then adding $\ell$ removes $p$ from the leaf set and adds $\ell$, so the number of leaves stays the same.
• If $de{g}_{T^{\prime }}(p)=2$, then in $T$ the vertex $p$ has degree $3$, so both the leaf count and the count of degree-at-least-$3$ vertices increase by $1$.
• If $de{g}_{T^{\prime }}(p)\ge 3$, then $p$ was already counted among the branching vertices, and adding $\ell$ only increases the leaf count.

In every case the inequality is preserved, so the claim holds for $T$. $■$

Two-Out-of-Three Property

Any graph $G$ satisfying two of the following properties must satisfy the third, and is therefore a tree:

• $G$ is connected
• $G$ is acyclic
• $G$ has $|V|-1$ edges

This gives a cheap tree test: count the edges and check either connectivity or acyclicity with a single BFS or DFS traversal.

One property alone is not enough

A two-component forest is acyclic without being connected. A triangle plus an isolated vertex has $|V|-1$ edges and still contains a cycle. The test needs two of the three properties.

Related notes

• graph fundamentals
• breadth-first search
• depth-first search
• Graphs and Trees Problems
• Graph Theory