Mader's splitting-off theorem

In an undirected graph G we denote by $$\lambda_G(u,v)$$ the maximum number of edge-disjoint paths between nodes u and v.

Theorem (Mader ). Let G=(V+s,E) be a connected undirected graph where the degree of s is not 3 and s is not incident to bridges. Then there are two edges incident to s that can be split off such that in the resulting graph $$G'$$ we have $$\lambda_{G'}(u,v)=\lambda_G(u,v)$$ for any $$u\in V$$ and $$v\in V$$ .

There is a directed splitting-off theorem due to Mader, too, but it concerns only global edge-connectivity.

Theorem (Mader ). Let D=(V+s,A) be a directed graph with $$\varrho_D(s)=\delta_D(s)$$ which is k-arc-connected in V for some positive integer k. Then for any arc $$st\in A$$ incident to s there exists another arc $$zs\in A$$ such that splitting off this pair of arcs the resulting graph is again k-arc-connected in V.

For a survey on applications and generalizations, see .