# Mader's splitting-off theorem

In an undirected graph *G* we denote by [math]\lambda_G(u,v)[/math] 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 [math]G'[/math] we have [math]\lambda_{G'}(u,v)=\lambda_G(u,v)[/math] for any [math]u\in V[/math] and [math]v\in V[/math].

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 [math]\varrho_D(s)=\delta_D(s)[/math] which is

*k*-arc-connected in

*V*for some positive integer

*k*. Then for any arc [math]st\in A[/math] incident to

*s*there exists another arc [math]zs\in A[/math] 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

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