True false question related to graph having a unique Minimum weight spanning tree

Question

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?

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

Daniel Fischer · Accepted Answer · 2014-10-08 22:23:12Z

3

ASCII art:

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

Consider the cycle $CDE$.

answered Oct 8 '14 at 22:23

Daniel Fischer♦

193k18 gold badges226 silver badges349 bronze badges

Add a comment |

1 Answer 1