Let n ≥ 3. Prove that a graph G on n vertices is a tree if and only if it is not isomorphic to $K_n$ and adding any edge (on the same vertex set) not present in G creates exactly one cycle.
I think this is a false statement, but it's in a highly reputable book so idk. Help me out. Could someone explain the proof if $G$ is not isomorphic to $K_n$ and adding any edge (on the same vertex set) not present in G creates exactly one cycle, it is a Tree?
$K_n$ is a complete graph of n vertices.
Thank you in advance
A tree has any two vertices connected by exactly one path. When you add an edge you turn that path into a circle. If a graph is not a tree, either there is a pair of unconnected vertices and you can join them without forming a cycle or there is already a cycle and joining any two vertices creates at least two more cycles.
I believe you are talking about simple graphs. The restriction on $K_n$ is just because you can't add any edges to it.