Let $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed 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
- $\Theta (\mid E \mid + \mid V \mid) \\$
- $\Theta (\mid E \mid \mid V \mid) \\$
- $\Theta(E \mid \log \mid V \mid) \\$
- $\Theta( \mid V \mid)$
