I currently studying about graphs and their algorithms, and i noticed a question which i don't know to to exactly prove:
If we have a connected, undirected graph G=(V,E), and every edge is with weight=1,is it true to say that every spanning tree that built from the shortest paths from the root, is a minimum spanning tree?
I ran some examples in http://visualgo.net/sssp.html and is seems for me that the answer for this question is true, but someone can show me how can i prove this? and another question that crossed my mind, does the other direction is also true?
Every tree has exactly n - 1 edges. Since all weights are equal to 1, every spanning tree of G has a total weight of n - 1. It is also true for the minimal spanning tree. So the answer is yes.