Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What is the most edge-connectivity you can guarantee in the remaining graph?
Formally: let $r(k)$ be $$\min_{G: k \textrm{ edge-connected}} ~~ \max_{T} ~~ \textrm{edge-connectivity}(G \backslash E(T))$$ where $T$ ranges over spanning trees of $G$, then what is $r(k)$?
I feel that in general, starting from a $k$-edge-connected graph, one should be able to leave edge-connectivity $k-o(k)$. However, the only useful bound I see so far is that "Every $2t$-edge-connected graph has $t$ spanning trees" implies $r(k) \ge \lfloor k/2 \rfloor - 1$. This is far from tight with respect to the best upper bound I can prove, $r(k) \le k-3$.
