# zbMATH — the first resource for mathematics

On a theorem of Mader. (English) Zbl 0789.05051
For vertices $$x$$, $$y$$ in a multigraph $$G$$, $$\lambda(x,y;G)$$ denotes the maximal number of edge-disjoint $$x,y$$-paths in $$G$$. Let $$G$$ be a finite multigraph and let $$s$$ be a vertex in $$G$$ of degree $$d(s) \neq 0,3$$ not incident to a bridge. For edges $$e_ i$$ joining $$s$$ and $$x_ i$$ for $$i=1,2$$, $$G^{e_ 1e_ 2}$$ arises from $$G$$ by deleting $$e_ 1$$, $$e_ 2$$, and, if $$x_ 1 \neq x_ 2$$, by adding a new edge between $$x_ 1$$ and $$x_ 2$$. It was proved in [W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3, 145-164 (1978; Zbl 0389.05042)] that there are edges $$e_ 1 \neq e_ 2$$ incident to $$s$$ such that $$\lambda (x,y;G^{e_ 1e_ 2})=\lambda (x,y;G)$$ for all vertices $$x,y$$ from $$G-s$$. Such a pair of edges is called a splittable pair at $$s$$. Now a relatively simple proof of this result is given, and it is shown that for $$d(s) \neq 3$$ there are $$\lfloor {d(s) \over 2} \rfloor$$ disjoint splittable pairs at $$s$$, whereas from the above result one gets for odd $$d(s)$$ only $${d(s)-3 \over 2}$$ such pairs.
Reviewer: W.Mader (Hannover)

##### MSC:
 05C40 Connectivity
##### Keywords:
theorem of Mader; multigraph; edge-connectivity; splittable pair
Full Text:
##### References:
  Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton Univ. Press Princeton, NJ · Zbl 0139.13701  Frank, A., Augmenting graphs to meet edge-connectivity requirements, SIAM J. discrete math., 5, 1, 25-53, (1992) · Zbl 0782.05054  Lovász, L., Lecture on a conference on graph theory, (1974), Prague  Lovász, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001  Mader, W., A reduction method for edge-connectivity in graphs, Ann. discrete math., 3, 145-164, (1978) · Zbl 0389.05042  Menger, K., Zur allgemeinen kurventheorie, Fund. math., 10, 96-115, (1927) · JFM 53.0561.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.