Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle

Question

When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it since that results in a graph with no cycles, therefore it must be a tree graph by definition?

Original statement to prove: Prove a simple connected graph T is a tree if and only if adding an edge between two existing vertices of T creates exactly one cycle.

Answer 1

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?

Answer 2

Hint:

• Prove that if connected graph $G = (V,E)$ contains a cycle and it is not a clique, then you can always add an edge that will create at least two cycles.
• Let $C \subset E$ be some cycle and $u \notin C$ be a vertex such that there exists two vertices $v_1, v_2 \in C$ with $uv_i \notin E$. Then one of $uv_i$ would create at least two cycles.
• If the previous step is not possible, then the graph is a clique or a clique without a single edge (and adding this missing edge surely would create at least two cycles).

Good luck!