enter image description hereWe have undirected weighted connective graph $G=(V,E)$, We also have a minimum spanning tree $T$ of $G$. Let $v$ be some vertex. We have new graphs, $G'$ and $T'$. $G'$ and $T'$ are same $G$ and $T$, except the extra node $v$ witch is connected (with new weighted edges) to the same nodes in both graphs. I need to prove that $G'$ MSP has the same weight as $T'$ MSP. I was thinking about using kruskal or prim algorithm to show that Given a MSP of $T'$, We can use kruskal or prim on $G'$ to find it, with no results.

Any idea?

  • $\begingroup$ I don't understand the construction of $G'$ and $T'$ $\endgroup$ – lox Nov 29 '19 at 18:16
  • $\begingroup$ Sorry I wasn't clear. $G' = ( V ⋃ $ {$v$} $ , E' )$. $E' = E ⋃ $ { $(u,v) | u ∈ V $}. $T'$ is defined similarly. $\endgroup$ – usert Nov 29 '19 at 18:26
  • $\begingroup$ So the new node $v$ is connected to all nodes in the original graph? $\endgroup$ – Throckmorton Nov 29 '19 at 18:37
  • $\begingroup$ Not necessarily, It can be connected to any node in $G$ and $T$. $\endgroup$ – usert Nov 29 '19 at 18:39
  • $\begingroup$ Added a small example. $\endgroup$ – usert Nov 29 '19 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.