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

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?

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.

• The third property is basically for an edge $e$, it defines a cut set in which it is the lightest. The property for MBST being an MST this cut set $C_e$ for every edge $e$ has weights greater than the bottleneck weight $w$... I'm still going through the proof and trying to understand the pieces. Commented Jan 30, 2021 at 12:24
• In this example, for the edge $3$, the cut set would be $\{2,3\}$, but these weights are not greater than $4$? Commented Jan 30, 2021 at 13:09
• @sprajagopal $C_{e}$ for edge $3$ would be ${5,3}$. Commented Jan 30, 2021 at 13:42
• @sprajagopal You have to look at the MST when you are removing an edge. Here, after you remove edge $3$. The partition $S_{e}$ contains edge $5$, and the other partition contains edges: $\{1,2\}$. Commented Jan 30, 2021 at 13:43