# How does the edge-connectivity of a graph change after deleting the edges of a spanning tree?

Let $k \in \mathbb{N}_{>0}$. An undirected graph $G=(V,E)$ is $k$-edge-connected, if after the removal of any set $E_{fail}$ of at most $k-1$ edges, the remaining graph $G'=(V,E \setminus E_{fail})$ is still connected.

Clearly, if $k$ pairwise edge-disjoint spanning trees for a node set $V$ exist, the union of those edges will give us a $k$-edge-connected graph (no matter what set of at most $k-1$ edges are deleted, at least one ''unharmed'' tree remains).

However, what happens in the other direction? Given a $k$-edge-connected graph, and the edges of a single spanning tree are removed, what is the edge-connectivity of the remaining graph?

I did some research, and found the following article as a start, http://www.sciencedirect.com/science/article/pii/0095895674900872, which states: a $k$-edge-connected graph has at least $\lceil(k-1)/2\rceil$ pairwise edge-disjoint spanning trees. However, I am not sure how to go further right now. Might you have some hints/tips?

Thank you!

• I don't know if that'll actually work, but you could consider a proof by induction over the number of edges. Here's the rough idea. Suppose the graph is $k$-connected, and you remove the edges of some arbitrary spanning tree. If the resulting graph is $(k - 2)$-connected, by induction there are at least $\lceil (k - 3)/2 \rceil$ remaining spanning trees. And $1 + \lceil (k - 3)/2 \rceil \geq \lceil (k - 1)/2 \rceil$. I don't know is the graph is $(k - 2)$-connected though - you think about it :) – Manuel Lafond Dec 1 '17 at 17:25

If a $k$-edge-connected graph has some large number of edge-disjoint spanning trees, that suggests that maybe we can carefully choose a spanning tree to remove without reducing the connectivity of the graph too much. But it is still possible that we may maliciously choose a spanning tree to remove and reduce the connectivity by a lot.
As an extreme example, suppose you have the graph $K_n$, which is $(n-1)$-connected. Remove a spanning tree in the form of a star: $n-1$ edges, all out of the same vertex. You leave a copy of $K_{n-1}$ and a single isolated vertex - not even a connected graph.