Let $G = (V,E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighted edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

When a new edge $e = (u, v)$ with weight $w(u, v)$ is added to the graph $G$, $T$ remains a spanning tree for $G \cup \{e\}$.

By the Cycle Property of MSTs:

• Adding $(u, v)$ to the tree $T$ introduces exactly one simple cycle, which consists of the new edge $(u, v)$ and the unique simple path between $u$ and $v$ in $T$.

• $T$ remains an MST of $G \cup \{e\}$ if and only if the newly added edge $(u, v)$ is the maximum weight edge (or tied for maximum weight) on this cycle. That is, $w(u, v) \ge w(e^{\prime})$ for all edges $e^{\prime}$ on the path between $u$ and $v$ in $T$.

Since $T$ is a tree with $|V|$ vertices and $|V|-1$ edges:

• Finding the unique path between $u$ and $v$ in $T$ and identifying the maximum weight edge on it can be done via standard graph traversal (DFS or BFS) on $T$.

• DFS or BFS on a tree with $|V|$ vertices takes time $O(|V| + (|V|-1)) = \Theta(|V|)$.

Thus, the worst-case time complexity is $\Theta(|V|)$, which corresponds to option D.