MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A graph has vertices m,n,o,p,q,rm,n,o,p,q,r and weighted edges mn:4,mo:7,no:3,op:6,oq:5,pq:2,pr:8,qr:7mn{:}4, mo{:}7, no{:}3, op{:}6, oq{:}5, pq{:}2, pr{:}8, qr{:}7, together with one more edge npnp whose weight is currently 99 (so npnp is not part of the minimum spanning tree). If npnp's weight were lowered, to what value would it need to drop so that the graph FIRST has two different minimum spanning trees (a tie)?