2
$\begingroup$

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.

$\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$
    – Pål GD
    Mar 9 at 18:35
  • 1
    $\begingroup$ Thank you, I didn’t think about that. $\endgroup$
    – CSstudent
    Mar 9 at 19:21

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.