First claim is incorrect as stated. It should be
$G$ is a tree if and only if $G$ is connected and erasing any edge will disconnect it. (otherwise two disconnected trees are a counterexample for the converse)
$\Rightarrow$ is easy. $G$ is connected by the definition of the tree. Now assume by contradiction that erasing some edge $uv$ doesn't disconnect it. Then, there is a path $P$ between $u$ and $v$ in $G\backslash uv$, but then $P \cup \{ uv \}$ is a cycle in $G$ contradiction.
$\Leftarrow$: $G$ is connected. Assume now by contradiction that $G$ contains a cycle $C$. Then erasing some edge from the cycle doesn't disconect it, contradiction.
Second claim is also wrong.
$G$ is a tree if and only if $G$ has no cycles and adding any edge will create a cycle. (otherwise any connected graph satisfies the second condition)
$\Rightarrow$ $G$ has no cycles by the definition of the tree. Now, we prove that adding any new edge will create a cycle.
Let $uv$ be any edge not in $G$. Since $G$ is a tree, it is connected, and thus there is a path $P$ between $u$ and $v$. Then adding $uv$ creates the cycle $P \cup \{uv\}$.
$\Leftarrow$: $G$ has no cycle. We need to show that $G$ is connected.
Let $u,v$ be vertices in $G$. If $uv$ is an edge we are done, otherwise, adding $uv$ will create a cycle $C$ which of course contains $uv$ as an edge. Erasing now $uv$ from this cycle, we are left with a path connecting $u$ and $v$.
The proof is not valid because it fails to prove that the graph is acyclic. The non sequitur is in the following:
$\dots$just remove that edge that created a cycle, then it since that results in a graph with no cycles
Notice that the statement doesn't follow. Also, notice that adding an edge to any connected graph will create a cycle. You must use the fact that exactly $1$ cycle is generated as a result.
Hint: Argue by contradiction. Assume the graph has a cycle. When you connect two vertices of the cycle, how many cycles are created?
Best Answer
Suppose $G$ is a tree — an undirected, acyclic, connected graph.
Suppose $a,b\in G$ and there is no edge from $a$ to $b$. Because $G$ is connected, there is a path from $a$ to $b$ in $G$: $$ a = x_1 \leftrightarrow x_2 \leftrightarrow \dotsc \leftrightarrow x_n = b, $$ where $n > 1$. Then adding an edge $a \leftrightarrow b$ creates a cycle $$ a = x_1 \leftrightarrow x_2 \leftrightarrow \dotsc \leftrightarrow x_n = b \leftrightarrow a, $$ of length $n+1$.