MathCastle
Graph TheorySuperchallengeGraph Algorithms

Graph Algorithms · Superchallenge problem

A graph has vertices 11–66 and weighted edges 12:3,13:8,23:2,24:6,34:5,35:4,45:7,46:9,56:112{:}3, 13{:}8, 23{:}2, 24{:}6, 34{:}5, 35{:}4, 45{:}7, 46{:}9, 56{:}1. Its minimum spanning tree includes edge 3434 (currently weight 55). If edge 3434's weight were increased, what is the largest value it could reach while the graph STILL has a UNIQUE minimum spanning tree that includes it (i.e. the value at which a tie first appears)?