# Minimum Spanning Tree with diameter 3

I need an $$O(|V||E|)$$ algorithm to detect if a graph has a minimum spanning tree with diameter 3.

This paper mentions that it is possible for any diameter by finding the vertex 1-center which can be done using Floyd's algorithm, but I need something much simpler only for the case of diameter 3.

• If a tree has diameter 3 then it is either a star or two stars "fused together", i.e. two vertices $x,y$ connected by an edge, so that all other vertex is connected by an edge to either $x$ or $y$. Does that help? May 20, 2021 at 11:48
• Thanks allot! Obviously this solves it... In this case all is needed is to find the MST, and then see if the tree which contain all edges of x and y weights the same... May 20, 2021 at 12:12

Perhaps the following helps:

If a tree has diameter 3 then either it is a single vertex, or there are two neighboring vertices $$x,y$$ such that every other vertex is a neighbor of either $$x$$ or $$y$$.

To see why this is true, consider a tree of diameter 3 with more than one vertex. If all vertices have degree 1, then the tree is of that form. Otherwise, let $$x$$ be a vertex of degree at least 2. If all neighbors of $$x$$ have degree 1, then you can designate one of them as $$y$$ and get the above structure. If $$x$$ has two different neighbors $$y,z$$ of degree at least 2 then the diameter is at least 4 (a neighbor $$y' \neq x$$ of $$y$$ is at distance 4 form a neighbor $$z' \neq x$$ of $$z$$), which is impossible. Therefore $$x$$ has a single neighbor $$y$$ of degree at least 2. Every vertex is thus either a neighbor of $$x$$ or a neighbor of $$y$$.