# 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.

• 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