Correctness of algorithm for computing diameter of a graph

Question

I am a TA for an introductory CS course, and one question given to students was how to use BFS to determine the diameter of a unweighted, undirected graph. The students were told they wouldn't be graded for efficiency, so the expected answer was a brute force algorithm where they ran BFS from every node to every other node and returned the maximum distance from these BFS runs. The students were provided with a BFS method they could reference in their pseudocode which took as an input a node and returned two mappings: one from each node in the graph to its distance from the start node (called distmap), and one from each node to its 'parent node' along the shortest path from the input node (called parentmap).

One student wrote the following algorithm:

1. Choose an arbitrary node from the graph and run BFS from it.
2. Create a set Temp of all the nodes that are not values in parentmap (i.e. the leaves of the BFS tree)
3. Initialize max_dist to 0
4. For each node n in Temp:
   1. Run BFS from n
   2. For each value d in distmap:
      1. IF d > max_dist THEN set max_dist equal to d
5. RETURN max_dist

I believe this answer is correct, but I am unable to prove it. Can someone prove why it works or provide a counterexample?

Answer 1

Maybe a slightly simpler counter-example:

It is quite clear that the maximum distance in this graph is between the green nodes (4), but if you start your BFS from the red node, Temp will consist of the two blue nodes only, which gives an incorrect "diameter" of 3.