Proving if $G$ has no cycles but by adding one edge between any two vertices will create a cycle then $G$ is a tree

Question

Prove: if $G$ has no cycles but by adding one edge between any two vertices it will create a cycle then $G$ is a tree. Below is the definition we use for a tree.

I don't see any way to connect the tree's definition and the assumption. I don't see what to suppose for the induction, since the assumption is for adding an edge and the conclusion is supposed to be reached by adding one more vertex and edge to a tree...

Do I have to add lemmas here?

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. (recursive definition)

Answer 1

See this question for a proof that a connected graph is a tree defined in this manner if and only if it has no cycles. Thus the only way $G$ can fail to be a tree is for it to be disconnected.

If $G$ is disconnected into two nonempty components $G_1$ and $G_2$ with no edges between them, then adding any edge from a vertex in $G_1$ to a vertex in $G_2$ will not create a cycle. To see this, suppose there is a cycle $C$ in the new graph. $C$ cannot be completely contained in either $G_1$ or $G_2$, hence both $C\cap G_1$ and $C\cap G_2$ are nonempty. For any vertices $v\in C\cap G_1$ and $w\in C\cap G_2$, any path from $v$ to $w$ must contain the new edge between $G_1$ and $G_2$. However, in order for $C$ to be a cycle we would need to have two paths from $v$ to $w$ that do not cross each other, hence the new graph contains no cycle. Thus $G$ is connected and hence a tree.

Answer 2

If a graph has no cycles and is not connected you can add an edge between two vertices in different components and no cycle will be created. If a graph is connected and has no cycles it is a tree.

Answer 3

HINT: Use the definition to prove by induction that every tree is connected, and no tree contains a cycle. Then prove the contrapositive of the desired statement. Assume that a graph $G$ is not a tree; either it contains a cycle, or it’s not connected. If you know that it contains no cycle, then it must not be connected. Now show that there must be a pair of vertices of $G$ such that adding the edge between them does not create a cycle.