How does Removing an Edge change Connectivity of a Graph

Question

Part of our homework. If I removed an edge of a k vertex-connected graph how would that impact the edge-connectivity?Our texbook has this proof:

Vertex-Connectivity(G) = k. Let G' be the graph obtained after removing k−1 vertices of G. If e is a bridge of G', then G'−e is disconnected and Vertex-Connectivity(G−e) >= k−1. If e is not a bridge, then G − e is connected and k(G − e) =k > k − 1.

Can someone explain this to me? This line "If e is a bridge of G', then G'−e is disconnected and Vertex-Connectivity(G−e) >= k−1" makes sense to me, but how would I prove it.

Answer 1

If $e$ is a bridge of $G'$, then $G'-e$ is disconnected

follows from the definition of a bridge. It's an edge whose removal increases the number of components.

and $\kappa(G-e) \ge k-1$. [I'm using $\kappa$ for vertex connectivity; this is standard.]

This should actually be an upper bound: $\kappa(G-e) \le k-1$. We've just discovered that there are $k-1$ vertices we can delete from $G-e$ to get $G'-e$, a disconnected graph. (They're the same number of vertices we deleted to get from $G$ to $G'$.) The vertex connectivity $\kappa(G-e)$ is the least number of vertices that will make this happen. So it's at most $k-1$. (It could be less, if there's a more efficient way.)

If $e$ is not a bridge, then $G' − e$ is connected and $\kappa(G − e) = k > k − 1$.

This, on the other hand, is just false. What we learn if $G'-e$ is connected is that this specific choice of $k-1$ vertices to delete from $G-e$ does not disconnect $G'-e$.

We can instead say the following. If, for every choice of $k-1$ vertices to delete from $G$ to get $G'$, $e$ is not a bridge of $G'$, then $\kappa(G-e) > k-1$. (That's because this tells us there's no way to remove $k-1$ vertices from $G'-e$ to get a disconnected graph.) Since we also know $\kappa(G-e) \le \kappa(G) =k$, we conclude $\kappa(G-e)=k$.

---

There is still something left to check. We've found two cases for $G-e$; one where $\kappa(G-e) \le k-1$, and one where $\kappa(G-e) =k$. (Technically, we haven't shown that both are possible, but there are plenty of examples you can cook up of each.)

The stronger thing we can say is that in the first case, $\kappa(G-e) = k-1$. To see this, you should show that if deleting $k-2$ vertices from $G-e$ disconnects it, then you can delete $k-1$ vertices from $G$ to disconnect $G$, and that contradicts $\kappa(G)=k$.