Say that you have $n$ friends. They each have preference weights for each other. (e.g. the edge between Bob and Alice is 10 and the edge between Bob and Carl is 0.5, meaning that Bob likes/wants to hang out with Alice 20x more than with Carl). Feel free to consider the graph undirected if considering the directed case is too hard. In fact, make whatever assumptions on the graph you need to get a meaningful result (e.g. the graph is bipartite describing how much each boy likes each girl and vice versa ala stable marriage).
If one finds the minimum/maximum spanning tree for this Relationship Graph, what is the significance of that graph? How should it be interpreted in terms of the reality of the situation? Or does it have no relevant interpretation/application with respect to reality?
Just something I can think of off the top of my head is: it provides the optimal infiltration route to befriend all $n$ friends. After you've befriended a node, you just keep asking to be introduced to the next friend along the MaxST path, till you've eventually met up with everyone. Conversely, the MinST is essentially the worst path to infiltrate a friend group through asking for introductions to other friends.
