# 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.

• If only you want to prove the implication, not the equivalence. – gukoff Mar 9 '13 at 6:22
• How do you deal with the complete graph? – Michael Biro Mar 9 '13 at 7:28

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?

• Ok..so can I use what I wrote as a proof or what for the converse – DJ_ Mar 9 '13 at 6:00
• Sorry, I had misread the question, and it took me a few minutes to regain my composure. – A.S Mar 9 '13 at 6:23
• For proving if T is a tree then adding an edge between 2 vertices creates exactly one cycle I used the definition that 2 vertices in T have exactly one path and so if I add a new edge it creates exactly one cycle. For the converse I did, since there is only one cycle in graph there is two paths from v to w in T, so if I remove one edge, the number of paths from v to w decreases by 1, so then its a tree. Sooo I can't remove an edge and just say the number of paths from v to w decreased to 1? – DJ_ Mar 9 '13 at 6:52
• The problem is that the hypothesis does not tell you that there is one cycle in the entire graph. It only tells you that adding an edge adds exactly $1$ cycle to the graph. – A.S Mar 9 '13 at 6:53
• well its an if and only if statement, don't I have to prove if adding an edge between two existing vertices of T creates exactly one cycle – DJ_ Mar 9 '13 at 6:56

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!