Trovare MST dopo aver aggiunto un nuovo vertice

Question

Lascia $ g = (v, e) $ che è non indirizzato e semplice. Abbiamo anche $ T $, un MST di $ g $. Aggiungiamo un vertice $ v $ al grafico e lo colleghiamo con bordi ponderati a alcuni dei vertici. Trova un nuovo MST per il nuovo grafico in $ O (| v | CDOT log | v |) $.

Fondamentalmente, l'idea sta usando Prim Algoritmo, inserendo solo i bordi di $ T $ più i nuovi bordi.

Non capisco perfettamente il motivo per cui funziona. Perché deve essere un albero di spanning minimo? Che ne dici di un caso in cui il vantaggio più pesante in $ t $ è $ 9 $ per esempio e abbiamo altri bordi nel grafico (e non in $ t $) con lo stesso peso?

È stato anche affermato che $ | v | -1 $ dei bordi debba essere dal vecchio grafico e l'altro sarà uno dei nuovi - non sono sicuro che sia nemmeno corretto. Cosa ne pensi?