# Weight of minimum spanning tree of G and T We 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?

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