Problem
COM-B2-M07-P005 An Added Edge
#5
★★☆☆☆ Level 2 of 5
One edge is added to a tree between two existing vertices. Prove that exactly one cycle appears.
In a tree, there was a unique path between the endpoints of the new edge.
Let the new edge join vertices \(u\) and \(v\). In the tree, there was exactly one simple path between \(u\) and \(v\). This path together with the new edge forms a cycle.
No other cycle can appear: any cycle after the addition must use the new edge, because there were no cycles before. Then the rest of that cycle would be another path between \(u\) and \(v\) in the tree, impossible.
A key fact for problems with \(n\) edges on \(n\) vertices.