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)
Best Answer
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.