Suppose $p$ be an maximal path in the graph $G.$
Let $u$ and $v$ be its end points.
Since p is the maximal path in the graph $G$ all the neighbours of $u$ and $v$ will be on the path $p.$
So, if we remove either $u$ or $v$ from the path $p$ then the neighbours of $u$ or the neighbours of $v$ remain connected through the path $p.$
Hence, after removing $u$ or $v$ from $G$ the graph $G$ remains connected.
Now, in the question we are told to give an algorithm to find the points $u$ and $v.$
The algorithm is given below
- STEP 1: Start
- STEP 2: Find a maximal path $p$ in the graph $G.$ (This would take $O(n)$ time.)
- STEP 3: The endpoints of that path are our required answer.
- STEP 4: STOP.