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

graph theorytrees

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.

Best Answer

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?

Best Answer

Related Solutions

[Math] $G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle – is the proof correct

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

Related Question