MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A graph has vertices w,x,y,z,vw,x,y,z,v and weighted edges wx:3,wy:5,xy:2,xz:8,yz:4,yv:7,zv:1wx{:}3, wy{:}5, xy{:}2, xz{:}8, yz{:}4, yv{:}7, zv{:}1. Its minimum spanning tree has weight 1010. What is the smallest possible total weight of a spanning tree that is NOT the minimum one (uses a different set of edges)?