New answers tagged minimum-spanning-tree
1
Let $n=|V|$ and $e=(x,y)$ be the new edge. Let $P$ be the unique path between $x$ and $y$ in $T$. Clearly $C = P + e$ is a cycle in $G+e$.
Let $f^* = \arg\max_{f \in P}{w(f)}$. $T$ is an MST of $G+e \iff w(e) \ge w(f^*)$.
The $\Rightarrow$ part:
If $w(e) < w(f^*)$ then $T - f^* + e$ is a spanning tree of $G+e$ of cost $w(T) - w(f^*) + w(e) < w(T)$, ...
3
Here is one such example of undirected weighted graph.
Top 50 recent answers are included
