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?
Best Answer
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.