2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yeah I think I got it. I know there is a sequence of blocks connecting any two by looking at the block graph. Within a block, the cut vertices are k edge connected. I can concatenate to find paths across blocks which are edge disjoint. $\endgroup$
    – user83387
    Apr 20, 2016 at 13:48

You must log in to answer this question.