Introduction to graph theory/Proof of Theorem 5

Statement

A tree of order $n$ has $n-1$ edges.

Corollary of

Theorem 4:For a graph $G$, the following are equivalent:

• $G$ is a tree
• $G$ is a minimal connected graph, in the sense that the removal of any edge will leave a disconnected graph.
• $G$ is a maximal acyclic graph, in the sense that the addition of any missing edge will create a cycle.

Proof

For $n=1$, all graphs have $0=n-1$ edges. For $n=2$, there are two graphs, one with an edge and one without. The graph without an edge is disconnected, and therefore is not a tree, whereas the one with an edge is connected and has no cycles and therefore is a tree.

For $n=3$, there are 4 graphs, one each with 0, 1, 2 or 3 edges. The graphs with 0 and 1 edges are disconnected, while the graph with 3 edges has a cycle. The graph with 2 edges is connected and has no cycle, so the theorem is proved for $n\le 3$.

Now suppose we have proved this theorem for all $n<k$, and let $T$ be a tree of order $k$. Remove an edge $e$ from $T$ to form a new graph $T-e$. By Theorem 4, $T$ is a minimal connected graph, and hence $T-e$ is disconnected. Any connected component of $T-e$ (by the connectedness of $T$) must have one of the vertices of $e$ in it, and hence $T-e$ has exactly two components.

The two components are connected, and have no cycles, and are therefore trees. Let there be $n_1,n_2$ vertices in the two components of $T-e$. Then $n_1+n_2=k$. Further, there are $n_1-1,n_2-1$ edges in the components, so $T-e$ has $k-2$ edges in total. Therefore, putting edge $e$ back into the graph, $T$ has $k-1$ edges.