Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle 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.
 A: 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?
A: 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!
