Number of Edges in Tree

Theorem

Let $T$ be a connected simple graph of order $n$.

Then $T$ is a tree iff the size of $T$ is $n-1$.

Proof

By definition, the order of a tree is how many nodes it has, and its size is how many edges it has.

Necessary Condition

Suppose $T$ is a tree with $n$ nodes. We need to show that $T$ has $n-1$ edges.

Proof by induction:

Let $T_n$ be a tree with $n$ nodes.

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition that a tree with $n$ nodes has $n-1$ edges.

Basis for the Induction

$P(1)$ says that a tree with $1$ vertex has no edges.

It is clear that $T_1$ is $N_1$, the edgeless graph, which has $1$ node and no edges.

So $P(1)$ is (trivially) true.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

Any tree with $k$ nodes has $k-1$ edges.

Then we need to show:

Any tree with $k+1$ nodes has $k$ edges.

Induction Step

Let $T_{k+1}$ be any tree with $k+1$ nodes.

Take any node $v$ of $T_{k+1}$ of degree $1$. Such a node exists from Tree has Degree One Nodes‎.

Let us consider $T_k$, the subgraph of $T_{k+1}$ created by removing $v$ and the edge connecting it to the rest of the graph.

By Subgraph of Tree, $T_k$ is itself a tree.

The order of $T_k$ is $k$, and it has one less edge than $T_{k+1}$ by definition.

By the induction hypothesis, $T_k$ has $k-1$ edges.

So $T_{k+1}$ must have $k$ edges.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

$\Box$

Alternative Induction Step

Let $T_{k+1}$ be any tree with $k+1$ nodes.

Remove any edge $e$ of $T$.

As $T_{k+1}$ has no circuits, $e$ must be a bridge, from Condition for an Edge to be a Bridge.

So removing $e$ disconnects $T_{k+1}$ into two trees $T_1$ and $T_2$, with $k_1$ and $k_2$ nodes, where $k_1 + k_2 = k+1$.

By the induction hypothesis, $T_1$ and $T_2$ have $k_1 - 1$ and $k_2 - 1$ edges.

Putting the edge $e$ back again, we see that $T_{k+1}$ has $\left({k_1 - 1}\right) + \left({k_2 - 1}\right) + 1 = k$ edges.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Strong Induction.

Therefore a tree with $n$ nodes has $n-1$ edges.

$\Box$

Sufficient Condition

Suppose $T$ is a connected simple graph of order $n$ with $n-1$ edges.

We need to show that $T$ is a tree.

Suppose that $T$ is not a tree. Then it contains a circuit.

It follows from Condition for an Edge to be a Bridge that there is at least one edge in $T$ which is not a bridge.

So we can remove this edge and obtain a graph $T'$ which is connected and has $n$ nodes and $n-2$ edges.

Let us try and construct a connected graph with $n$ nodes and $n-2$ edges.

We start with the edgeless graph $N_n$, and add edges till the graph is connected.

We pick any two vertices of $N_n$, label them $u_1$ and $u_2$ for convenience, and use one edge to connect them, labelling that edge $e_1$.

We pick any other vertex, label it $u_3$, and use one edge to connect it to either $u_1$ or $u_2$, labelling that edge $e_2$.

We pick any other vertex, label it $u_4$, and use one edge to connect it to either $u_1, u_2$ or $u_3$, labelling that edge $e_3$.

We continue in this way, until we pick a vertex, label it $u_{n-1}$, and use one edge to connect it to either $u_1, u_2, \ldots, u_{n-2}$, labelling that edge $e_{n-2}$.

That's the last of our edges, and we still haven't connected the last vertex.

Therefore a graph with $n$ vertices and $n-2$ edges that such a graph can not be connected.

Therefore we can not remove any edge from $T$ without leaving it disconnected.

Therefore all the edges in $T$ are bridges.

Hence $T$ can contain no circuits and so must be a tree.

$\blacksquare$

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 4.1$: Theorem $4.2$, Exercise $9$