Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition/Induction Step/Proof 1

Theorem

Let the following hold:

For all $j \le k$, a tree of order $j$ is of size $j - 1$.

Then this holds:

A tree of order $k + 1$ is of size $k$.

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

Take any node $v$ of $T_{k + 1}$ of degree $1$.

Consider $T_k$, the subgraph of $T_{k + 1}$ created by removing $v$ and the edge connecting it to the rest of the tree.

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

We have by hypothesis that $T_k$ has $k - 1$ edges.

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

$\blacksquare$