I have been recently teaching Graph Theory to second year students. Amongst the things we covered in class were minimal spanning trees. The topic inspired me the following problem.

Let us consider a fully connected graph with vertex all labelled from to . A weight is associated to each edge . We define

,

with and real numbers.

Depending of the values of and , what can we say about the minimal spanning tree of ? Is it unique ? If not how many spanning trees are there ?

Advertisements