0
$\begingroup$

In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks

  • 2
    No, as a counterexample take a triangle with weights $4, 5, 6$ on edges.2012-06-01
  • 0
    Thanks but in your example, the path from any vertex that we choose to be the start vertex to one of the other 2 vertices is still the minimal between those 2 though. That's the property of triangle inequality, isn't it?2012-06-01
  • 0
    I can't understand your comment. Consider the graph with vertices $a, b, c$ and edges $ab, bc, ca$ with assigned weights $4, 5, 6$. Then the spanning tree with minimal weight is $ab, bc$, but the shortest put from $a$ to $c$ is $ac$. Is this not correct?2012-06-01
  • 0
    My question is: if b is the first vertex we use to create the MST, is ba and bc the minimum cost path from b to any other vertex? The first vertex is important in my question because we may have different MST's if we start from different vertex.2012-06-01
  • 0
    So this is an example showing that your assertion as stated is not correct, because you may be starting from the vertex $a$.2012-06-01
  • 0
    Oh, I see. Thank you.2012-06-01

1 Answers 1