Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles.
$\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles.
$\Leftarrow$ $G$ is connected and acyclic, prove $G$ is a tree. Suppose $G$ isn't a tree, then it must be either disconnected or has cycles which contradicts the given.
It seems too easy so I'm doubting myself…
Definition for a tree: If $n=1$ then $G$ is a tree. If $|V|>1$ then $G$ is a tree if G is given from from a tree $T$ by adding $1$ vertex and $1$ edge connected to it.
Best Answer
Clearly a tree with 1 vertex has no cycles. For a connected tree with $k$ vertices, pick a vertex that was most recently added in some sequence constructing the tree. If we remove the vertex, there are no cycles by induction. If we had a cycle when we attached the new vertex, then the cycle would have to contain the new vertex, which means the new vertex would have to have degree at least 2, contradicting the choice of vertex. Thus a tree has no cycles by induction.
Suppose now that $G$ is a connected graph with no cycles. If $G$ has one vertex, then it is a tree. Otherwise, suppose there is a vertex $v$ of degree 1. Then $G-v$ is a connected graph with no cycles and hence a tree by induction. It easily follows that $G$ is a tree.
Thus we may assume that every vertex has degree at least 2. Choose a vertex $w$ such that $G-w$ is connected and let $u,v$ be distinct vertices adjacent to $w$. Then there is a path from $u$ to $v$ not containing $w$ since $G-w$ is connected, and adjoining $w$ to this path creates a cycle. Thus a connected graph with no cycles has at least one vertex of degree 1, and we are done.
Here is justification that $w$ can be chosen so that $G-w$ is connected:
Suppose $G=\{v_1,v_2,\ldots,v_k\}$. Set $w_1=v_1$. Inductively, assume $\{w_1,w_2,\ldots,w_p\}$ is a set of $p$ distinct vertices such that for all $p'\leq p$ we have that $\{w_1,w_2,\ldots,w_{p'}\}$ is connected. Let $\{v_{i_1},v_{i_2},\ldots,v_{i_{k-p}}\}$ be the remaining vertices in $G$. If there is no $q\leq p$ and $j\leq k-p$ such that $\{w_q,v_{i_j}\}$ is an edge in $G$, then $\{w_1,w_2,\ldots,w_p\}$ and $\{v_{i_1},\ldots,v_{i_{k-p}}\}$ are disjoint, have no edges between them, and their union is $G$, implying that $G$ is disconnected. Thus there exists a $w_{p+1}\in \{v_{i_1},\ldots,v_{i_{k-p}}\}$ such that $\{w_1,\ldots,w_{p+1}\}$ is connected, and we are done.