I'm trying to prove a statement "given a graph G=(V,T) and that no cycle C exists that contains only edge "e" and other edges that their weight is smaller than that of "e", prove that "e" must be in some mst". I tried to proof by contradiction, but I'm not sure what I can say about "e" when it never belongs to any mst.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Do you know kruskal's algorithm? What would it mean for $e$ to never be part of an MST? Well, when you consider it, its two endpoints are always already in the same component. How can that be? $\endgroup$– John KemenyCommented Mar 9 at 18:35
-
1$\begingroup$ Thank you, I didn’t think about that. $\endgroup$– CSstudentCommented Mar 9 at 19:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Suppose that you run Kruskal's algorithm, which computes an MST by repeatedly adding the cheapest edge that does not create a cycle.
In any run of Kruskal, when we consider your edge $e = uv$, it turns out that $u$ and $v$ are already in the same connected component.
That means that there is a path from $u$ to $v$ where every edge is strictly cheaper than $e$.
Hence $e$ must be the heaviest edge in a cycle.
