# Introduction to graph theory/Proof of Theorem 5

Jump to navigation Jump to search

## Statement

A tree of order ${\displaystyle n}$ has ${\displaystyle n-1}$ edges.

## Corollary of

Theorem 4:For a graph ${\displaystyle G}$, the following are equivalent:

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

## Proof

For ${\displaystyle n=1}$, all graphs have ${\displaystyle 0=n-1}$ edges. For ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n\leq 3}$.

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

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