# Mader's splitting-off theorem

Jump to: navigation, search

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 [1]). 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 [2]). 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 [3].

## References

1. W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978), 145-164, Google Books link
2. W. Mader, Konstruktion aller n-fach kantenzusammenhängenden Digraphen, Europ. J. Combinatorics 3 (1982), 63-67, DOI link
3. A. Frank, Edge-connection of graphs, digraphs, and hypergraphs, DOI link, EGRES Technical report