Finding the maximum length of a minimum spanning tree

Question

Graph G has 4 vertices/nodes and 5 edges. It is also connected. Its edges have the following weights: 5, 8, 10, 16, 18.

The minimum length for a minimum spanning tree of graph G would be 5+8+10 which is 23.

But what would the maximum length for a minimum spanning tree of graph G be? and how would I go about calculating it?

Answer 1

I'll first consider the case with no parallel edges. Considering Kruskal's algorithm edges with weights 5 and 8 would be taken with any possible structure of the graph. Then if edges 5, 8 and 10 doesn't form a cycle Kruskal's algorithm will take edge with weight 10 and finish its work. Hence in optimal graph edges 5, 8 and 10 form a cycle. I'll denote the vertices of this cycle as $A$, $B$ and $C$. The fourth vertex will be denoted as $D$ Then edge of weight 16 have to connect $D$ with $A$ or $B$ or $C$ since parallel edges are not allowed. So, Kruskal's algorithm will take it and finish its work. The answer in that case is $5+8+16=29$

The case with parallel edges is more obvious. Kruskal's algirithm have to take edge with weight 5. Then graph with vertices $\{A,B,C,D\}$ and three edges between $A$ and $B$ with weights 5,8 and 10, edge between $B$ and $C$ with weight 16 and edge between $C$ and $D$ with weight 18 gives us maximal possible answer.

Answer 2

There are $\binom42=6$ potential edges between the vertices, so only one edge is missing, so the structure of $G$ is fully determined:

1-2
|\|
3-4

The minimal spanning tree uses the minimum of the weights incident at $2$, the minimum of the weights incident at $3$ and the minimum of the three remaining weights. Thus its length is maximised by putting $16$ and $18$ together, e.g. incident at $2$, leading to a maximal minimal spanning tree length of $5+8+16=29$.