# For every undirected unweighted graph is every MST also a SPT

I have a feeling this might be wrong an I'm looking for a counter example, however, I couldn't find one yet.. can anyone guide me in the right direction?

• What's the definition of an MST in an unweighted graph? – lox Jun 24 '19 at 21:33
• Perhaps the following question and the examples given there are helpful: Minimum spanning tree vs Shortest path. – Hendrik Jan Jun 24 '19 at 22:07
• @IOX: I think you can just assume it's like a weighted graph but all edges have the same weight (or just say have weight 1). Hendrik: thanks! – user106782 Jun 24 '19 at 22:15
• if all edges have the same weight, then any tree has a weight of $w(V-1)$, which makes any tree MST. I think you meant to ask the question with a weighted graph. In which case the answer is no. – lox Jun 24 '19 at 22:44
• Since every tree in an unweighted graph is an MST, your question asks whether every tree is a shortest path tree. It looks like this is true if and only if the given graph is acyclic. – mo2019 Jun 29 '19 at 12:06

Counter example: V={a,b,c,d}, E={(a,b), (a,c), (a,d), (b,c)}. A MST of this graph, rooted at a, could be: {(a,b), (a,d), (b,c)}. But this is not a SPT because the path a->c is of length 2 instead of 1 (a and c are directly connected in the original graph).
• Does this make sense: I have a graph G = (V,E) with V = {A,B,C} and E = {(A,B), (B,C), (A,C)} and say my MST G' has edges {(C,A), (C,B)} it's not a SPT when I set the root of the SPT at A. Therefore not every MST is a SPT. – user106782 Jun 24 '19 at 21:36