2
$\begingroup$

Consider a graph graph G with |V| vertices and more than |V|-1 edges, is it possible for an edge to be the 'heaviest' and also be unique, but still be part of the graph's MST? If so, in which cases is it applicable?

From what I've been thinking so far, if the maximum edge is the only part that connects some vertex with the rest of the tree, it has to be part of the MST regardless, but that is regardless of the constraint of having more than |V| - 1 edges.

So am I correct to assume that, having more than |V| - 1 edges you can have the heaviest edge as part of the MST? Also, why is the constraint of edges being more than |V| - 1 applied here, what purpose does it serve?

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Consider the following example:

enter image description here

You can clearly see that the heaviest edge (connecting vertices 3 and 4) is in any MST of this graph. In general, the heaviest edge (assuming it is unique) will be part of the MST of a graph if and only if it is a bridge (meaning that if we remove that edge the graph gets disconnected). The condition $|E| \geq |V| - 1$ doesn't really change anything. However, in order for MST to make sense, we need the graph to be connected. Note that $|E| \geq |V| - 1$ does not guarantee that.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ The condition $|E| \geq |V| - 1$ does NOT guarantee that the graph is connected. In your graph, you could delete the $10$ edge, and have a non-connected graph with $|E| = |V| - 1$. However, it is the converse that is true: a connected graph will always verify $|E| \geq |V| - 1$. $\endgroup$
    – Nathaniel
    Apr 27, 2021 at 22:08
  • $\begingroup$ You're right. I am editing my answer. $\endgroup$
    – Giorgos Giapitzakis
    Apr 27, 2021 at 22:09
  • $\begingroup$ So the criteria that E > |V| - 1 doesn't really serve a purpose then? $\endgroup$
    – csmango
    Apr 27, 2021 at 22:26
  • $\begingroup$ No, it doesn't. Perhaps it should be replaced with the condition that $G$ is connected. $\endgroup$
    – Giorgos Giapitzakis
    Apr 27, 2021 at 22:59

Your Answer

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

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