CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
Jakkie Chan
Jakkie Chan

Reputation: 317

Is an adjacent lightest edge in an MST

In an undirected and connected graph, if e is the lightest edge adjacent to a vertex v, then is e part of some MST?

I said yes because an MST has all the lightest edges chosen, is this correct thinking?

Upvotes: 1

Views: 265

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Let T be a minimum weight spanning tree and vw be a lightest edge incident to v. Let P be the unique path in T between v and w. If P is not vw itself, then it contains some other edge vx. Let T' be the set of edges derived from T by inserting vw and removing vx. I claim (1) T' is at least as light as T, since vw is at least as light as vx (2) T' is a tree, since it connects everything (for each walk in T, derive a related walk in T' with the same endpoints by replacing vx with vw and the rest of P) and has the right number of edges, hence (3) T' is a minimum weight spanning tree that contains vw.

Upvotes: 1

Related Questions