# How much must deleting a spanning tree reduce edge-connectivity?

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$.

• Out of curiosity, how do you prove the upper bound r(k)≤k−3? – Tsuyoshi Ito Sep 6 '10 at 12:29
• Take a $k$-regular $k$-edge-connected graph with no Hamiltonian path. Since it is non-Hamiltonian, the spanning tree must have degree 3 at some vertex. Thus the remainder has degree at most $k-3$ at some vertex. – Dave Pritchard Sep 7 '10 at 9:29