# Spanning tree that maximizes all-pairs bandwidth => Maximum spanning tree?

Let $$G = (V, E)$$ be a weighted, undirected graph, with $$f: E \to \mathbb{R}$$ its weight function. Given a path $$P = (e_1, \dots, e_k)$$, we call $$\operatorname{bwd}(P) = \min_{1 \le i \le k} f(e_i)$$ the "path-bandwidth" of $$P$$. Let $$\mathcal{P}_G(v, w)$$ be the set of paths between two vertices $$v, w \in V(G)$$. Given two vertices $$v, w \in V$$, we call $$\operatorname{bwd}_G(v, w) = \operatorname{max}_{P \in \mathcal{P}_G(v, w)}{\operatorname{bwd}(P)}$$ the bandwidth in $$G$$ between $$v$$ and $$w$$. That is, the maximum path-bandwidth of any path in $$G$$ between $$v$$ and $$w$$.

If $$T$$ is a spanning tree of $$G$$, $$\operatorname{bwd}_T(v, w) = \operatorname{bwd}(P)$$ where $$P$$ is the path from $$v$$ to $$w$$ in $$T$$. We call $$T$$ a "maximum pairwise bandwidth spanning tree" (MPBST) when $$\operatorname{bwd}_T(v, w) = \operatorname{bwd}_G(v, w)$$, for all $$v, w \in V$$.

It is easy to show that every maximum spanning tree is a MPBST.

Experimentally the converse seems to hold: Every MPBST is a maximum spanning tree. Is this true, and if so, why?

I tried proving this using induction in the minimum symmetric difference between an MPBST and the set of all maximum spanning trees of $$G$$, to show via edge swaps I can make an MPBST of the same weight as the original one, but closer and closer in symmetric difference to this set. I could not finish the argument unless I assumed all weights were distinct.

• If you can prove the case when all weights are distinct, applying the usual perturbation technique can show the general case. Commented Feb 28, 2022 at 7:15

Yes, it is true that every MPBST is a maximum spanning tree.

Here is a characterization of maximum spanning Tree(MST). A proof for that characterization can be found here.

Given a spanning Tree $$T$$ of $$G$$, $$T$$ is an MST $$\iff$$ for any edge $$uv\notin T$$, $$uv$$ has the minimal weight among edges in the cycle created by adding $$uv$$ to $$T$$.

Suppose $$S$$ is an MPBST. Let us prove $$S$$ is an MST.

Let edge $$uv\notin S$$. Let $$P$$ be the path from $$v$$ to $$u$$ in $$S$$, i.e., the cycle created by adding $$uv$$ to $$S$$ is $$P$$ followed by edge $$uv$$.

Since $$((u,v))$$ is a path from $$u$$ to $$v$$, $$\operatorname{bwd}_G(u, v)\ge\operatorname{bwd}_{((u,v))}(u,v)=w((u,v))$$.

Since $$S$$ is an MPBST, $$\operatorname{bwd}(\text{the path from }v\text{ to }u\text{ in }S)=\operatorname{bwd}_S(u,v) = \operatorname{bwd}_G(u, v)\ge w((u,v)),$$ i.e., edge $$(u,v)$$ has the minimal weight among edges in the cycle created by adding $$uv$$ to $$S$$. By the characterization of MST, $$S$$ is an MST.

• Thanks for the characterization! Indeed it's very useful in this case. Commented Feb 28, 2022 at 16:12