Size of Tree is One Less than Order/Sufficient Condition

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let the size of $T$ be $n-1$.


Then $T$ is a tree.


Proof

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


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 Edge to be 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 was the last of our edges, and the last vertex still has not been connected.


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

Therefore we cannot 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