Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights?

Question

I can see a counterexample such as this:

But I can also see in some cases it could be the same. I am trying to understand what property makes a MBST also a MST?

Answer 1

Let $G = (V,E)$ be the input graph. And, let $G_{M} = (V,E_{M})$ be an MST of this graph. First, note the following properties of the MST and BMST.

1. An MST is always a BMST

2. If all edges in the graph have distinct edge weights, there is always a unique MST.

3. Let $e$ be any edge in $E_{M}$. Let $(S_{e},V \setminus S_{e})$ be the cut obtained after removing $e$ from the graph $G_{M}$ and $C_{e}$ denote the edges of $G$ that goes across this cut. Then, $e$ is the minimum weight edge among the edges in $C_{e}$.

Following is the property that is required for a BMST to be an MST.

Property: Every BMST is an MST if and only if for every $e \in E_M{}$, all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$, where $w$ denote the weight of the bottleneck edge in a BMST or MST.

Proof: First, let us prove the 'only if' direction.

($\to$) Suppose every BMST is an MST. For the sake of contradiction assume that there is an edge $e \in E_{M}$ such that there exist an edge $e'$ in $C_{e} \setminus \{e\}$ that has weight smaller than $w$. Let us remove $e$ from $G_{M}$ and add $e'$ to $G_{M}$. Let this new graph is $G_{M}'$. It is easy to see that this graph is a BMST. However, it is not an MST since

$$\begin{align} Total\_Weight(G_{M'}) &= Total\_Weight(G_{M}) - w(e) + w(e')\\ &> Total\_Weight(G_{M}) \end{align}$$ Here, I have used the fact that $w(e) < w(e')$ by Property 3 of MST. This contradicts the fact that every BMST is an MST. This completes the proof of the 'only if' direction. Now, let us prove the 'if' direction.

($\gets$) Suppose for every $e \in E_{M}$, all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$. For the sake of contradiction, assume that there is a BMST $G_{B} = (V_{B},E_{B})$ that is not an MST. Therefore, we can say that there is an edge $e$ in $E_{M}$ that is not in $E_{B}$. Now, remove this edge form the graph $G_{M}$ and let $(S_{e}, V \setminus S_{e})$ be the corresponding cut. Let $u$ be a vertex in $S_{e}$, and $v$ be a vertex in $V \setminus S_{e}$. Let $p$ be a path from $u$ to $v$ in $G_{B}$. It means, there exist an edge $e' \in p$ that goes across the cut. In other words, $e'$ belongs to $C_{e}$. Now, note that since $e' \in G_{B}$, the weight of $e'$ is $\leq$ $w$. It contradicts the fact that all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$. This prove the 'if' direction. Hence the proof is complete.