Option a $\iff$ Option b $\iff$ Option c $\iff$ Option d.
- You need at least $n-1$ edges to have a connected graph. This leaves no edges to make any cycles. Thus, Option a $\implies G$ is acyclic.
- A connected graph with $n-1$ edges is acyclic, as shown above. Now, if we add any more edges to this graph, we will be connecting two vertices that are already connected. Thus, adding any more than edges to a connected graph will cause cycles. So, if a graph is acyclic and connected, it has exactly $(n-1)$ edges.
- You can't fit $(n-1)$ edges between $(n-1)$ vertices without causing cycles. Thus, if graph with $(n-1)$ edges is acyclic, it must connect $n$ vertices. Hence, an acyclic graph with $(n-1)$ edges is connected.
Thus, all options, a to d are equivalent.
Option b $\iff G$ is a tree.
- Any acyclic connected graph is a tree by definition.
- A graph $G$ is a tree if it is both acyclic and connected by definition.
Thus, all options a to d are both necessary and sufficient for an undirected graph $G$ to be a tree.
Option e $\mathrel{\rlap{\hskip .5em/}}\Longrightarrow G$ is a tree.
- Since $G$ is not constrained to be acyclic, we can create a cyclic graph with $(n-1)$ edges. This graph will be cyclic, and it won't be connected. And thus, it won't be a tree.
Hence, option E is the correct answer.
