What happens when an additional edge is added to a tree?
Options
- A. The graph becomes disconnected
- B. A cycle is created
- C. The number of vertices decreases
- D. More than one of the above
- E. None of the above
Quiz Practice:
B. A cycle is created
A tree is connected and contains no cycles. If an additional edge is added between any two vertices already in the tree, there is already a unique path between those vertices. The new edge together with that path forms exactly one cycle. Therefore, adding any extra edge to a tree destroys its acyclic property. This is why a tree with N vertices has exactly N - 1 edges.