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!

  • 1
    $\begingroup$ 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 :) $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Thanks! The complete graph example answers the question for me :-) $\endgroup$ – cs_student_273 Dec 2 '17 at 17:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.