# Can a graph with more than |V| - 1 edges have the maximum weighted edge as part of its MST?

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. 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.
• 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$. Apr 27, 2021 at 22:08
• No, it doesn't. Perhaps it should be replaced with the condition that $G$ is connected. Apr 27, 2021 at 22:59