Let G be a k-edge-connected graph with n ≥ 3. For any e ∈ E(G), show that G/e is k-edge- connected.

Question

Could someone help me with this question. My thought is that proof by contradiction. But I don't know which direction should I start with...

Answer 1

First, we must be careful with the definitions here. Consider any $k$-edge-connected graph which has a vertex $u$ of degree $k$ with two neighbors $v,w$ that are also adjacent to each other. Then contracting edge $vw$ will reduce the degree of $u$ to $k-1$, disproving the claim...

...unless we make sure to define the contraction $G/vw$ as a multigraph, so that a vertex $u$ adjacent to both $v$ and $w$ will have two parallel edges to the contracted vertex $G/vw$. This preserves the degree.

---

With the multigraph definition, while we could do tricky things, just reasoning from the definition works.

There is a bijection between the edges in $G$ other than $e$ and the edges in $G/e$: edges to an endpoint of $e$ become edges to the contracted vertex.

All paths in $G$ remain paths in $G/e$ under this bijection: if a path simply passes through an endpoint of $e$, it now passes through the contracted vertex, and if it uses $e$, it becomes shorter.

A set of edges $S$ is a cut if we can find two vertices $x,y$ such that all $x-y$ paths contain an edge of $S$. By the observation above, if $S$ is an edge cut in $G/e$, the image of $S$ under the bijection is an edge cut in $G$. Assuming $G$ is $k$-edge-connected, the cut in $G$ has at least $k$ edges, and therefore the cut in $G/e$ must have had at least $k$ edges.