0
$\begingroup$

If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?

MST means minimum spanning tree of a graph. I came across these two posts:

and I follow both until the case where $w_{old}>w$ and $e\notin T$. They both say that deleting the heaviest edge will guarantee an MST, but I don't see how to prove that. The cycle property just says that IF you have an MST, it can't have an edge which is the heaviest edge in a cycle of the original graph $G$; it is NOT saying that IF you have a tree that doesn't contain an edge that happens to be the heaviest edge of some cycle in the original graph $G$, you are an MST.

To make the question more explicit in terms of the problem it was trying to solve, I will copy a part of the first link:

If its weight was reduced, add it to the original MST. This will create a cycle. Scan the cycle, looking for the heaviest edge (this could select the original edge again). Delete this edge.

I don't understand why this guarantees that we find an MST. Sure, we get a spanning tree but why does deleting this heaviest edge yield a MINIMUM spanning tree?

$\endgroup$
3
  • $\begingroup$ Definition? What is MST? $\endgroup$ Commented Feb 8, 2020 at 18:14
  • $\begingroup$ Good question. Please see my answer here. $\endgroup$
    – Apass.Jack
    Commented Feb 11, 2020 at 11:50
  • $\begingroup$ By the way, cross-posting is not recommended. $\endgroup$
    – Apass.Jack
    Commented Feb 11, 2020 at 11:51

2 Answers 2

1
$\begingroup$

Your line "IF you have an MST, it can't have the heaviest edge in a cycle" is a little odd. If you have a tree (including an MST), it can have no cycles. Consequently no edge (including the heaviest edge) can be in a cycle.

Suppose that you have a tree, $T$, a subgraph of a graph, $G$, that $e$ is an edge of $G$ with vertices $a$ and $b$, and that adding $e$ to $T$ produces a cycle.

Claim: Adding $e$ to $T$ cannot produce more than one cycle. Suppose $C_1 + e$ and $C_2 + e$ are two cycles produced by inserting $e$. Then $\{a,b\} \subset C_1 \cap C_2$ and we see $C_1 + C_2$ is a cycle in $T$. Since $T$ is a tree, there are no cycles in $T$. By contradiction, we have shown the claim.

Since $T+e$ contains only one cycle, $C+e$, deleting any edge, $f$, from $C+e$ yields graph that is an acyclic tree. The graph is acyclic because we have broken the only cycle. The graph is a tree because any path $P_1{-}f{-}P_2$ connecting two vertices can be replaced with the path $P_1{-}C{-}P_2$, preserving connectivity.

$\endgroup$
5
  • 1
    $\begingroup$ But why is deleting the heaviest edge going to produce a minimum spanning tree? $\endgroup$
    – D.R.
    Commented Feb 8, 2020 at 18:27
  • $\begingroup$ From every cycle in $G$, you must delete at least one edge. If you do not delete the maximal edge, you do not get a minimal spanning tree. By contrapositive, ... $\endgroup$ Commented Feb 8, 2020 at 21:27
  • 2
    $\begingroup$ Your answer did not address the question. I'm sorry, but I don't see how your claim has anything to do with my question. $\endgroup$
    – D.R.
    Commented Feb 8, 2020 at 21:55
  • $\begingroup$ @D.R. : I guess we'll just have to agree to disagree. $\endgroup$ Commented Feb 8, 2020 at 22:15
  • $\begingroup$ @EricTowers if you don't delete a maximal edge, then you do not get an MST. However that doesn't not necessarily mean that "if you do delete a maximal edge, then you do get an MST." $\endgroup$
    – xdavidliu
    Commented Dec 27, 2020 at 4:15
0
$\begingroup$

If you already have an MST, then any edge e you add to it will itself be guaranteed to be a maximal weight edge on the resulting cycle. If the resulting cycle had an edge that had higher weight than e, then you would be able to remove it and keep e, which contradicts your claim that we began with an MST.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .