[Math] Adding one edge to a tree creates exactly one cycle

trees

I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?

Best Answer

This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.

Best Answer

Related Solutions

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

[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