I have to give an algorithm that finds two nodes whose distance is at least half of the diameter of a graph (Given an undirected connected graph G), knowing that the diameter of a graph is the largest distance between any two nodes. The nodes are unweighted.
The general idea is to run BFS from any arbitrary node, and find two nodes that fulfill the requirement but the difficulty for me lies in formally proving any claim used.
Is a possible solution to have an algorithm that runs BFS from a node to calculate the diameter, and then in the stored list to find two nodes that are at least half that diameter? Or is there a more optimal solution?
I am a first year CS student, so any guidance or help would be appreciated!