Equivalent characterizations of a tree

We show (i) connected and acyclic $\implies$ (ii) connected with $n-1$ edges $\implies$ (iii) acyclic with $n-1$ edges $\implies$ (i), which chains all three together.

**(i)$\implies$(ii)**, by induction on $n$. The base case $n=1$ is immediate: a single vertex has $0 = n-1$ edges. For the inductive step, take a connected acyclic graph $T$ on $n\ge2$ vertices. Since $T$ is finite and acyclic, it must contain a leaf $v$ (a vertex of degree $1$): otherwise every vertex would have degree $\ge 2$, and following edges out of any starting vertex without immediately backtracking would eventually revisit a vertex, producing a cycle. Deleting $v$ and its one incident edge leaves a graph $T'$ on $n-1$ vertices that is still connected ($v$ had no other vertices depending on it to stay connected) and still acyclic (a subgraph of an acyclic graph is acyclic). By the inductive hypothesis, $T'$ has $(n-1)-1$ edges, so $T$ has $(n-1)-1+1 = n-1$ edges.

**(ii)$\implies$(iii)**. Suppose $T$ is connected with $n-1$ edges. If $T$ had a cycle, deleting one edge of that cycle would keep the graph connected (the two endpoints of the deleted edge are still joined by the rest of the cycle), giving a connected graph on $n$ vertices with only $n-2$ edges. But any connected graph on $n$ vertices needs at least $n-1$ edges (each new vertex beyond the first needs at least one new edge to reach it), so $n-2$ edges cannot connect $n$ vertices — a contradiction. So $T$ has no cycle, i.e. it is acyclic.

**(iii)$\implies$(i)**. Suppose $T$ is acyclic with $n-1$ edges, and let it have $c$ connected components. Each component is itself connected and acyclic, so by the already-proven direction (i)$\implies$(ii) applied to each component separately, a component with $n_i$ vertices has $n_i - 1$ edges. Summing over all components, the total edge count is $\sum_i (n_i - 1) = n - c$. Since the total is given as $n-1$, we get $n - c = n - 1$, so $c=1$: $T$ is connected.