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

  • $\begingroup$ Out of curiosity, how do you prove the upper bound r(k)≤k−3? $\endgroup$ Sep 6, 2010 at 12:29
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 7, 2010 at 9:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.