MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
I see. Thanks! – Tsuyoshi Ito Sep 15 '10 at 22:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.