I am facing the following problem: Given an **undirected complete Euclidean weighted** graph $ G(V, E)$ and its **MST** $ T$ . I need to **remove** an arbitrary vertex $ v_i \in V(G)$ , and given a vertex $ v_j \notin V(G)$ , I have to calculate the MST of $ G^{‘}((V(G) \backslash \{v_i\})\cup\{v_j\}, (E\backslash\{(v_i, v_k): v_k \in V(G)\})\cup\{(v_k, v_j): v_k \in V(G^{‘})\})$ , i.e, the graph $ G$ with the vertex $ v_j$ (and its respective edges) and without the vertex $ v_i$ (and its respective edges). To solve this, we can apply some well-know MST algorithms, such as Prim’s, Kruskal’s, Borukva’s algorithm. Neverthless, if we do this we would not use the already existing MST $ T$ , i.e., we would calculate a new whole MST. So, I would like to know if there is any way to reuse the existing MST $ T$ .

There are two a similar question to this here (with edges, considering only the removing of them), and here (with vertex, considering only the adding of them).