Trouver MST après avoir ajouté un nouveau sommet

Question

Soit $ g = (v, e) $ qui n'est pas dirigé et simple. Nous avons également $ T $, un MST de $ g $. Nous ajoutons un sommet $ v $ au graphique et le connectons avec des bords pondérés à quelques des sommets. Trouvez un nouveau MST pour le nouveau graphique dans $ o (| v | cdot log | v |) $.

Fondamentalement, l'idée utilise Timide Algorithme, ne mettant en place les bords prioritaires que les bords de $ T $ plus les nouveaux bords.

Je ne comprends pas complètement la raison pour laquelle cela fonctionne. Pourquoi doit-il être un arbre couvrant minimum? Qu'en est-il d'un cas où le bord le plus lourd de $ T $ coûte 9 $ par exemple, et nous avons d'autres bords dans le graphique (et non dans $ T $) avec le même poids?

Il a également été affirmé que $ | v | -1 $ des bords devait provenir de l'ancien graphique et l'autre sera l'un des nouveaux - je ne suis pas sûr que ce soit même correct. Qu'est-ce que tu penses?