# Is the following algorithm for finding the minimum diameter spanning tree correct?

You are given an undirected and unweighted connected graph $G(V, E)$ for which you've been asked to find a spanning tree that has minimum diameter.

I have an idea but I'm not sure if it's a correct one. Can you give me a feedback?

The algorithm:

let T be an empty forest of trees for v in V color v white for v in (max-to-min-sort V by degree) color v gray for u in adj(v) if u is white add (v, u) to T mark u gray mark v black 

The algorithm works on the same principal as Kruskal's algorithm for a MST.

Thank you for your time

• From what I can see, it does yield a tree (provided $G$ is connected). I would try applying the algorithm to regular graphs and see if it does what you want. I'm skeptical that it gives a min-diameter tree... and I suspect a counter-example can be found among regular graphs. (I haven't been able to find one yet myself though.) – TravisJ May 8 '15 at 11:28
• The reason I think a regular-graphs are where to look is because your algorithm tries to make use of high (relative) degree vertices. But, if the graph is regular, then I can add vertices (the v ones that become black first) in any order I want... and I can add their neighbors in any order I want. – TravisJ May 8 '15 at 11:32
• Do not waste your time - the algorithm is extremely buggy. You can see how much using the "Petersen graph". And it does not even builds a tree : / – user931392 May 8 '15 at 12:19