0
$\begingroup$
  • You have an undirected graph $G$
  • $G$ has a cycle in it
  • That cycle has an edge $e$
  • e is a unique lightest weight edge in that cycle

Is it true that $e$ is part of every Minimum weight spanning tree of $G$?

I cant find any example to disprove this statement so I am assuming it is true. Do you think the same? or can you find a counter example?

$\endgroup$
2
  • $\begingroup$ Does $G$ have only that one cycle, or can it have others? $\endgroup$ – Daniel Fischer Oct 8 '14 at 22:15
  • $\begingroup$ @DanielFischer it can have other cycles also $\endgroup$ – Krimson Oct 8 '14 at 22:16
3
$\begingroup$

ASCII art:

    A---1---B
    |\     /|
    | 1   1 |
    |  \ /  |
    1   C   1
    |  / \  |
    | 2   3 |
    |/     \|
    D---4---E

Consider the cycle $CDE$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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