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)
Answer
5
Explanation
The diagonals BD and AC (weights 1 and 3) are in every MST: BD is the unique lightest edge at D (DA = 6, DC = 8) and AC is the unique lightest edge at A (AD = 6, AB = 7). Together they form two pieces, {A, C} and {B, D}.
A spanning tree on 4 vertices has 3 edges, so exactly one more edge must join the two pieces. The candidates are BC = \(x\), AD = 6, AB = 7 and CD = 8. BC is in every MST only if it is strictly the lightest of these, i.e. \(x \lt 6\).
At \(x = 6\), BC ties with AD and {BD, AC, AD} is an MST without BC. So the largest integer value is 5.
Answer: 5