[Math] A connected graph $G$ is $k$-edge-connected $\iff$ each block of $G$ is $k$-edge-connected.

graph theory

A graph $G$ is $k$-edge-connected if every disconnecting set of edges (i.e. edge set D such that $G' = (V, E \setminus D)$ is disconnected) has at least $k$ edges.

A block of a graph is a maximal connected subgraph with no cut vertex.

I know that it's possible to write $G = B_1 \cup \dots \cup B_n$ as a union of its blocks. I tried working through a version of Menger's theorem which tells me $G$ is $k$-edge-connected $\iff$ it contains $k$ edge-disjoint pants between any two vertices $u, v$. I hoped that this would help show the forward direction that $G$ being $k$-edge-connected implies that its blocks were, and I think it does (all the edge-disjoint paths between two vertices $u, v \in V(B_i)$ must lie within the block due to maximality).

However, I'm having trouble showing the reverse: if blocks are $k$-edge-connected then the graph $G$ is as well. I'm not sure how to think about finding edge-disjoint paths for vertices in different blocks.

Best Answer

Two blocks share at most one vertex. Think about how the neighbourhood of that vertex must look like to satisfy k-edge connectivity in both blocks.

Related Question