Size of Tree is One Less than Order
Theorem
Let $T$ be a connected simple graph of order $n$.
Then $T$ is a tree if and only if the size of $T$ is $n-1$.
Proof
By definition:
and:
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_{>0}$, let $\map P n$ be the proposition that a tree with $n$ nodes has $n-1$ edges.
Basis for the Induction
$\map 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 $\map P 1$ is (trivially) true.
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
Then we need to show:
Induction Step: Proof 1
Let $T_{k + 1}$ be an arbitrary tree with $k + 1$ nodes.
Take any node $v$ of $T_{k+1}$ of degree $1$.
Such a node exists from Finite Tree has Leaf Nodes.
Consider $T_k$, the subgraph of $T_{k + 1}$ created by removing $v$ and the edge connecting it to the rest of the tree.
By Connected Subgraph of Tree is 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 hypothesis, $T_k$ has $k - 1$ edges.
So $T_{k + 1}$ must have $k$ edges.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
$\Box$
Induction Step: Proof 2
Let $T_{k + 1}$ be any tree with $k + 1$ nodes.
Remove any edge $e$ of $T_{k + 1}$.
By definition of tree $T_{k + 1}$ has no circuits
Therefore from Condition for Edge to be Bridge it follows that $e$ must 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 hypothesis, $T_1$ and $T_2$ have $k_1 - 1$ and $k_2 - 1$ edges.
Putting the edge $e$ back again, it can be seen that $T_{k + 1}$ has $\paren {k_1 - 1} + \paren {k_2 - 1} + 1 = k$ edges.
Therefore a tree of order $k+1$ is of size $k$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
$\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.
Aiming for a contradiction, suppose $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.
Hence, by Proof by Contradiction, $T$ must be a tree.
$\blacksquare$
Beware
Just because a simple graph $G$ has an order one greater than its size does not necessarily make it a tree.
$G$ still has to be connected.
Take this simple graph, for instance: