CLRS Appendix B: Equivalent conditions for trees

A tree is a connected, acyclic (undirected) graph. Let $G = (V,E)$ be an undirected graph. Here are some equivalent conditions for $G$ to be a tree:

$G$ is a tree.
Any two vertices in $G$ are connected by a unique simple path.
$G$ is connected, but if any edge is removed from $E$, the resulting graph is disconnected.
$G$ is connected, and $\lvert E\rvert= \lvert V\rvert-1$.
$G$ is acyclic, and $\lvert E\rvert = \lvert V\rvert-1$.
$G$ is acyclic, but if any edge is added to $E$, the resulting graph contains a cycle.

I will roughly prove their equivalence here.

$(1) \Rightarrow (2)$: Since $G$ is connected, any two vertices $u, v$ are connected by at least one simple path. If there exists more than one such path between $u$ and $v$, then $G$ contains a cycle (Contradiction).

$(2) \Rightarrow (3)$: Suppose we remove edge $(u,v)$. If there still exists a path between $u$ and $v$, then there would have more than one simple path connecting $u$ and $v$ initially (Contadiction). Thus $u$ and $v$ must not be connected after the removal of $(u,v)$ so the resulting graph is disconnected.

$(3) \Rightarrow (4)$: Prove by strong induction (see (A) below).

$(4) \Rightarrow (5)$: Suppose $G$ contains cycles. Remove edges from cycles in $G$ until we get an acyclic graph $G'=(E',V')$. Note that $G'$ is still connected, so $\lvert E'\rvert \geq \lvert V'\rvert - 1$. However, $\lvert E\rvert = \lvert V\rvert -1$, so this implies we have removed 0 edges! Thus $G$ must have been acyclic$$.

$(5) \Rightarrow (6)$: See (B) below.

$(6) \Rightarrow (1)$: Suppose there is no path connecting $u$ and $v$ in $G$. Then add the edge $(u,v)$ to $G$. This new edge cannot have formed a cycle (Contradiction). Thus $G$ must have been connected initially.

Additionally, here are two more useful facts: (can be proven via strong induction)

A. $G$ is connected $\Rightarrow \lvert E\rvert \geq \lvert V\rvert-1$.

B. $G$ is acyclic $\Rightarrow \lvert E\rvert \leq \lvert V\rvert-1$.