Question

The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).

 

Hint:

When solving for the edges that must be included in a minimum spanning tree, compare the edge in question to the weights of other edges and ensure that no other edge can replace it without increasing the overall weight of the spanning tree.

Answer 1

Correct Answer: 5

For an edge to appear in every minimum spanning tree, it must be unavoidable: whenever the graph is divided into two parts by removing that edge, all other edges connecting those two parts must have strictly larger weights.

Removing the edge between B and C separates the graph into two regions. Any alternative way of reconnecting these two regions would have to use one of the other edges incident on either B or C.

From the graph, the lightest edge that can reconnect these regions has weight \(5\). If the weight \(x\) of edge B–C exceeds this value, an MST can be formed that avoids this edge by choosing a cheaper alternative.

Therefore, to guarantee that B–C is always selected, its weight must not exceed the smallest competing edge weight.

Hence, the maximum value of \(x\) is \(\boxed{5}\).