Mader 1973 ein extremalproblem des zusammenhangs von graphen

../

examples_p228: Mader's 1973 examples showing that no constant c_n makes (n/2)e(G) + c_n edges force two vertices joined by n internally disjoint paths, for odd n ≥ 5 and even n ≥ 6: from an (n − 2)-regular graph with m cut cliques and a universal vertex, graphs with (n/2)(e − 1) + m(n/2 − 2), or m(n − 5), edges and no two vertices joined by n such paths; the disproof of the vertex-disjoint form of the Bollobás–Erdős conjecture the site records as k_m(n) > (m/2)n + C.

korollar: Mader's exact edge-disjoint threshold: every graph with more than (n/2)(e(G) − 1) edges has two vertices joined by n edge-disjoint paths, and for every m ≥ n ≥ 2 there is a graph on m vertices with [(n/2)(m − 1)] edges and no such pair; in the site's notation ℓ_m(n) = [(m/2)(n − 1)] + 1, which is 1 + n·C(m,2) at the problem's parameters.

satz_1: Mader's theorem that every finite graph G on at least n vertices with more than (n/2)(e(G) − 1) − (1/2)σ_n(G) edges, σ_n(G) the sum over vertices of degree below n − 1 of their degree deficits, contains two vertices joined by n edge-disjoint paths; the edge-disjoint form of the Bollobás–Erdős conjecture for every n.

satz_2: Mader's girth-restricted vertex-disjoint bound: for n ≥ 4, every finite graph G of girth at least n + 2 with at least n + 1 vertices and more than (n/2)(e(G) − (n − 1)) edges contains two vertices joined by n paths that pairwise share only their ends.

---

W. Mader, Ein Extremalproblem des Zusammenhangs von Graphen, Math. Z. 131 (1973), 223--231 (the header of p. 223 prints "Math. Z. 131, 223--231 (1973)" and "© by Springer-Verlag 1973"; the DOI 10.1007/BF01187240 and the issue number 3 are not printed and come from the Crossref record cited on the problem page); "Eingegangen am 14. November 1972" (received 14 November 1972, p. 231); the author at the "II. Mathematisches Institut der FU", D-1000 Berlin 33, as printed on p. 231 (page image and text layer; FU is the Freie Universität). Cited as [Ma73] on the problem page. The copy read for this card is the publisher's version of record; no preprint or repository version is known here. Its seven references (p. 231) are [1] Bollobás, On graphs with at most three independent paths connecting any two vertices, Studia Sci. Math. Hungar. 1 (1966), 137--140, the problem page's [Bo66] (not held); [2] Erdős and Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, math.-naturw. R. 12 (1963), 251--258; [3] Harary, Graph Theory (Addison-Wesley, 1969); [4] Leonard, On graphs with at most four line-disjoint paths connecting any two vertices, J. Combinat. Theory Ser. B 13 (1972), 242--250, filed as leonard_1972_graphs_at_most_four_line_disjoint_paths_connecting_any_two_vertices; [5] Mader, Existenz gewisser Konfigurationen in $n$-gesättigten Graphen und in Graphen genügend großer Kantendichte, Math. Ann. 194 (1971), 295--312; [6] Mader, Kantendisjunkte Wege in Graphen, "Eingereicht bei den Monatsh. Math." (submitted); and [7] Wagner, Graphentheorie (Bibliographisches Institut, 1970). The paper is reference [9] of the filed sorensen_thomassen_1974_k_rails_graphs, which reports both of its results for the problem on p. 143, and the value of its Korollar is the formula that the filed Leonard 1972 proves for $r\le5$ and leaves open for $r>5$ on p. 250; the filed leonard_1973_graphs_ways is the $n=6$ proof that footnote 1 of p. 223 reports from an oral communication.

The copy read for this card is the publisher's per-article PDF, a scan of the printed article: 9 pages, printed pp. 223--231 = PDF pp. 1--9 (printed p. $n$ is PDF p. $n-222$), generated from a TIFF scan in January 2005 per the file's metadata (creator "304232005.TIF", producer PageGenie PDFGenerator), with an OCR text layer that locates passages but garbles the umlauts, the Greek letters of the notation ($\kappa$, $\lambda$, $\gamma$, $\sigma$ and $\mu$ come out as Latin letters and digits), the inequality signs, the subscripts and every displayed formula. Provenance: the copy was obtained from the publisher on 2026-09-22 as a DRM-free PDF, the DOI https://doi.org/10.1007/BF01187240 resolving to the article; 403,224 bytes. The file prints "© by Springer-Verlag 1973" on its first page (the OCR text layer renders the symbol as "9"), every other right reserved.

Read status: claims checked for the introduction with its footnote 1, the notation and Satz 1 (p. 223), the identities (1) and (2) (p. 224), the Korollar with its proof (pp. 226--227), the definition of type $n$ (p. 227), the passage on the vertex-disjoint problem with its examples and their edge counts (pp. 228--229), Satz 2 with (X) and footnotes 3 and 4 (p. 229) and the closing remarks (p. 231), each read clause by clause on the page images of PDF pp. 1, 2, 4, 5, 6, 7 and 9 on 2026-09-22; p. 231 was read on the page image for the reference list, the address and the received date. The proof of Satz 1 (pp. 223--226) was read on the page images of PDF pp. 1--4 for structure (the induction on the number of vertices, the separating edge set $T$, the graphs $\bar G_\nu$ and $G'_\nu$, the assertion (A) and the cases I--III); the structural results (Z) and (Y) with their proofs (pp. 227--228) and the proofs of (X) and of Satz 2 (pp. 230--231) were read on the page images for structure only. None of the steps was checked. The edge counts of the examples of p. 229 were recomputed here (below). Nothing here is independently reviewed.

Contents

• Introduction and notation (p. 223, page image). The paper opens with its question: how many edges a graph with a given number of vertices can have without containing two vertices joined by $n$ edge-disjoint paths ("kantendisjunkte Wege"). Conventions, quoted: "Sei $e(G)$ die Anzahl der Ecken, $\kappa(G)$ die Anzahl der Kanten des endlichen, ungerichteten, schlingenlosen Graphen $G$ ohne mehrfache Kanten" ($e(G)$ the number of vertices, Ecken, and $\kappa(G)$ the number of edges, Kanten, of a finite undirected loopless graph without multiple edges). The announcement, quoted: "Es wird bewiesen, daß in jedem Graphen $G$ mit $\kappa(G)>\frac n2(e(G)-1)$ zwei Ecken existieren, die durch $n$ kantendisjunkte Wege verbunden sind, und diese Abschätzung ist bestmöglich" (it is proved that in every graph $G$ with $\kappa(G)>\frac n2(e(G)-1)$ two vertices exist that are joined by $n$ edge-disjoint paths, and this estimate is best possible). The next sentence attributes the case $n=4$ to [1] and the case $n=5$ to [4], and footnote 1 adds that, by an oral communication of Bollobás, Leonard has proved the inequality for $n=6$ as well. The paper also derives properties of the extremal graphs and closes with the analogous question for vertex-disjoint paths ("eckendisjunkte Wege"). Notation: $E(G)$ and $K(G)$ the vertex and edge sets; $[x,y]=[y,x]$ the edge between $x$ and $y$; $\lambda(x,y;G)$ the maximum number of edge-disjoint paths between $x\ne y$ in $G$; $\gamma(x,G)$ the degree of $x$; and, displayed, $\bar\lambda(G):=\max_{x\ne y}\lambda(x,y;G)$, $E_m(G):=\{x\in E(G)\mid\gamma(x,G)\le m\}$, $e_m(G):=|E_m(G)|$ and $\sigma_n(G):=e_0(G)+e_1(G)+\cdots+e_{n-2}(G) =\sum_{x\in E_{n-1}(G)}(n-1-\gamma(x,G))$, $n$ a natural number. A filing note: a vertex of degree $d\le n-1$ is counted by $e_d,\ldots,e_{n-2}$, that is $n-1-d$ times, so the two forms of $\sigma_n$ agree; $e_m(G)$ counts vertices of degree at most $m$, as the site's thread reads it, not of degree exactly $m$.
• Satz 1 and its proof (pp. 223--226; the statement on the page image of PDF p. 1, the proof on the page images of PDF pp. 1--4 for structure), paged at satz_1. Quoted: "Satz 1. Jeder endliche Graph $G$ mit $\kappa(G)>\frac n2(e(G)-1)-\frac12\sigma_n(G)$ und $e(G)\ge n$ enthält zwei Ecken $x$ und $y$ mit $\lambda(x,y;G)\ge n$." The proof first counts edges by degrees: if $E_{n-1}(G)=E(G)$ then (1) $\kappa(G)=\frac{n-1}2e(G)-\frac12\sigma_n(G)$, and if exactly one vertex has degree at least $n$ then (2) $\kappa(G)\le\frac n2(e(G)-1)-\frac12\sigma_n(G)$ (p. 224). Then induction on the number of vertices, supposing $\bar\lambda(G)<n$: since $\frac{n-1}2e(G)\le\frac n2(e(G)-1)$ for $e(G)\ge n$, (1) and (2) give two vertices $a_1$, $a_2$ of degree at least $n$; Menger's theorem (cited to Wagner [7], Satz 9.3) gives a set $T$ of edges separating them with $|T|=\lambda(a_1,a_2;G)<n$, $G-T$ the disjoint union of $G_1\ni a_1$ and $G_2\ni a_2$, and $C_\nu$ the set of endpoints of $T$ in $G_\nu$. The induction hypothesis applied to $\bar G_\nu:=(E(G)-R_\nu,K(G)-K(G_\nu))$ gives (3) $|C_1|+|C_2|>n$ (pp. 224--225). For the graphs $G'_\nu$ obtained from $G$ by identifying the vertices outside $G_\nu$ to one vertex $A_\nu$, the assertion (A) $\lambda(x,y;G'_\nu)\le\lambda(x,y;G)$ for $x,y\in E(G_\nu)$ is proved by rerouting a path through $A_\nu$ along two of the $a_1$--$a_2$ paths, so $\bar\lambda(G'_\nu)<n$ (p. 225); and the induction hypothesis, or (1) for a $G'_\nu$ with $e(G'_\nu)\le n$, applied to $G'_1$, $G'_2$ in three cases (I, $e(G'_1)\ge n$ and $e(G'_2)\ge n$; II, $e(G'_1)\le n$ and $e(G'_2)\ge n$; III, $e(G'_1)\le n$ and $e(G'_2)\le n$) gives (4) $|C_1|+|C_2|<n$ through the displayed inequalities ($\beta$), ($\gamma$), ($\delta$), the identity ($\beta'$) from (1) and the sharpenings ($\gamma'$), ($\gamma''$) of ($\gamma$), against (3) (pp. 225--226). Footnote 2 (p. 225) defines $W[a,b]$ as the subpath of a path $W$ between $a$ and $b$.
• Korollar and its proof (pp. 226--227, page images), paged at korollar. Quoted: "Korollar. Für jeden Graphen $G$ mit $\kappa(G)>\frac n2(e(G)-1)$ gilt $\bar\lambda(G)\ge n$. Zu jeder ganzen Zahl $m\ge n\ge2$ existiert ein Graph $G$ mit $e(G)=m$, $\kappa(G)=\bigl[\frac n2(e(G)-1)\bigr]$ und $\bar\lambda(G)<n$." Proof: $e(G)>n$ follows from the edge count, so the first claim is Satz 1; for the second, when $m$ is odd or $n$ even there is (by the Erdős--Gallai criterion, Harary [3], Satz 6.2, or by factorizations of complete graphs) a graph on $m$ vertices with one vertex of degree $m-1$ and all others of degree $n-1$, and when $m$ is even and $n$ odd one with one vertex of degree $m-1$, one of degree $n-2$ and all others of degree $n-1$; it has $\bigl[\frac n2(e(G)-1)\bigr]$ edges "und es ist offensichtlich $\bar\lambda(G)<n$" (and obviously $\bar\lambda(G)<n$).
• The extremal graphs (pp. 227--228; the definition on the page image, the rest for structure). A graph with one vertex of degree $e(G)-1$ and all others of degree less than $n$ is "vom Typ $n$" (of type $n$). The paper contrasts the cases: by [1], for $n=4$ every 2-connected graph $G$ with $\kappa(G)=\frac n2(e(G)-1)$ and $\bar\lambda(G)<n$ is of type $n$, whereas for every $n\ge5$ there are, the paper says, easily given 2-connected extremal graphs with arbitrarily many vertices that are not of type $n$ (no construction is printed). For $G$ with $e(G)>n\ge2$, $\kappa(G)=\frac n2(e(G)-1)-\frac12\sigma_n(G)$ and $\bar\lambda(G)<n$ and two vertices of degree at least $n$: $|C_1|+|C_2|=n$, $|T|=n-1$ and equality in ($\delta$), ($\beta$) and ($\gamma$) (or ($\gamma'$), ($\gamma''$)); (Z) at most one vertex of $C_1$, and of $C_2$, is incident with two or more edges of $T$; the graph $H:=(C_1\cup C_2,T)$ is a tree with at least $e(H)-2$ leaves; and (Y) there are $y_1\in C_1$, $y_2\in C_2$ with $[y_1,y_2]\in T$ such that every edge of $T$ is incident with $y_1$ or $y_2$, so $G$ splits "längs $[y_1,y_2]$" (along that edge) into two extremal graphs $G'_1$, $G'_2$. For 2-connected $G$, by Satz 1 of [6] the set $T$ can be chosen so that one component has exactly one vertex of degree at least $n$, which is $y_1$, and $G'_1$ is of type $n$. Remarks (p. 228): with the hypothesis weakened to degree at least $n-1$ the same holds for $T$, so $G$ is $(n-1)$-edge-connected when $\sigma_n(G)=0$; and in a graph $G$ with $\kappa(G)=\frac n2(e(G)-1)-\frac12$, $\sigma_n(G)=0$ and $\bar\lambda(G)<n$ a smallest edge set separating two vertices of degree at least $n$ need not have the form (Y), and $|T|=n-2$ can occur.
• The vertex-disjoint problem (pp. 228--229, page images), paged at examples_p228. Notation: $\mu(a,b;G)$ the maximum number of paths between $a\ne b$ that pairwise share only $a$ and $b$, $\bar\mu(G)=\max_{a\ne b}\mu(a,b;G)$, and $\tau(G)$ the girth ("Taille"). The question: how many edges a graph with $e(G)=m$ and $\bar\mu(G)<n$ can have. For $n\le4$ the extremal graphs are the same as for edge-disjoint paths, by [1]; for $n\ge5$ the paper says the problem seems "keine einfache Lösung zuzulassen" (to admit no simple solution); the related problem of the maximal number of edges without two adjacent vertices $a$, $b$ with $\mu(a,b;G)\ge n$ was solved in [5]. Then, quoted: "Die folgenden Beispiele zeigen, daß keine Konstante $c_n$ mit der Eigenschaft existiert, daß für jeden endlichen (2-fach zusammenhängenden) Graphen $G$ mit $\kappa(G)\ge\frac n2e(G)+c_n$ gilt $\bar\mu(G)\ge n$" (the following examples show that no constant $c_n$ exists such that every finite, 2-connected, graph $G$ with $\kappa(G)\ge\frac n2e(G)+c_n$ has $\bar\mu(G)\ge n$). The construction, for odd $n\ge5$ (in parentheses, even $n\ge6$): a connected graph $G'$, regular of degree $n-2$, containing $m$ disjoint complete graphs $H_1,\ldots,H_m$ with $e(H_\mu)=n-2$ (resp. $n-3$) such that $G'-K(H_\mu)$ falls into $n-2$ (resp. $n-3$) components for every $\mu$; "Solche Graphen lassen sich ohne Schwierigkeit angeben" (such graphs can be given without difficulty), with footnote 3 that for even $n$ no graphs of the first kind exist and for odd $n\ge7$ the second construction also works. $G$ is $G'$ with a new vertex $A$ joined to every vertex of $G'$; then $\kappa(G)=\frac n2(e(G)-1)$ and $\mu(a,b;G)=n-2$ (resp. $n-3$) for $a\ne b$ in $E(H_\nu)$. $\bar G$ adds, for odd $n$, a new vertex $x_\mu$ joined to every vertex of $H_\mu$ for each $\mu$, and for even $n$ two new vertices $x^1_\mu$, $x^2_\mu$ each joined to every vertex of $H_\mu$ and to each other. Quoted: "Dann ist auch noch $\bar\mu(\bar G)<n$ und es gilt $\kappa(\bar G)=\frac n2(e(\bar G)-1)+m(\frac n2-2)$ (bzw. $\kappa(\bar G)=\frac n2(e(\bar G)-1)+m(n-5)$)." Edge counts recomputed here: $\kappa(G)=\frac{n-2}2e(G')+e(G')=\frac n2(e(G)-1)$; for odd $n$, $e(\bar G)=e(G)+m$ and $\kappa(\bar G)=\kappa(G)+m(n-2) =\frac n2(e(\bar G)-1)-\frac{mn}2+m(n-2)=\frac n2(e(\bar G)-1)+m(\frac n2-2)$; for even $n$, $e(\bar G)=e(G)+2m$ and $\kappa(\bar G)=\kappa(G)+2m(n-3)+m=\frac n2(e(\bar G)-1)+m(n-5)$, as printed. The absence of $n$ internally disjoint paths in $\bar G$ is asserted, not argued. The passage closes with the remark that if "kleine" (small) cycles are forbidden, in particular the complete graphs $V_m$ with $m\ge3$, then $\kappa(G)>\frac n2(e(G)-1)$ does force $\bar\mu(G)\ge n$.
• Satz 2 (pp. 229--231; the statement, (X) and the footnotes on the page image of PDF p. 7, the proofs and the closing remarks on the page images of PDF pp. 8--9), paged at satz_2. Quoted: "Satz 2. Jeder endliche Graph $G$ der Taille $\tau(G)\ge n+2$ mit $\kappa(G)>\frac n2(e(G)-(n-1))$ und $e(G)\ge n+1$ enthält zwei Ecken $a$ und $b$ mit $\mu(a,b;G)\ge n$, falls $n\ge4$ ist" (every finite graph of girth at least $n+2$ with more than $\frac n2(e(G)-(n-1))$ edges and at least $n+1$ vertices contains two vertices joined by $n$ internally disjoint paths, for $n\ge4$), with footnote 4 that by a theorem of Erdős and Sachs [2] graphs satisfying these hypotheses exist. (X): every graph with $e(G)\ge n+1$, $\tau(G)\ge n+2$ and $\kappa(G)>\frac n2(e(G)-(n-1))$ contains, for $n\ge4$, at least two vertices of degree at least $n$; proved (p. 230) by counting edges around a shortest cycle $C$ and the set $N$ of vertices adjacent to it, each adjacent to exactly one vertex of $C$ since $\tau(G)>4$. Proof of Satz 2 (pp. 230--231): induction on $e(G)$; a vertex set $T$ with $|T|=n-1$ whose removal leaves parts $G'_1$, $G'_2$ of at least two vertices each gives $\bar\mu(G)\ge n$ by the induction hypothesis and an edge count; by (X) there are vertices $x_1\ne x_2$ of degree at least $n$, and if $\mu(x_1,x_2;G)<n$ Menger's theorem supplies such a $T$, directly when $[x_1,x_2]\notin K(G)$ and, when $[x_1,x_2]\in K(G)$, from a separating set $T'$ of $G-[x_1,x_2]$ with $|T'|=n-2>0$ enlarged by one of $x_1$, $x_2$, using $\tau(G)>3$. Closing remarks (p. 231): Satz 2 also holds for $n\le3$, the pentagon being the only exception, for $n=3$; sharpenings hold, for instance $\bar\mu(G)\ge4$ for every graph with $\kappa(G)>2(e(G)-3)$, $e(G)\ge6$ and $\tau(G)\ge5$ up to one exception, and $\bar\mu(G)\ge8$ for every graph with $\kappa(G)>4(e(G)-7)$, $e(G)\ge10$ and $\tau(G)\ge6$; Satz 2 "legt die Vermutung nahe" (suggests the conjecture) that every graph with $\kappa(G)>\frac n2(e(G)-1)$ and $\bar\mu(G)<n$ must contain triangles, though such a graph need not contain a $V_4$ (a complete graph on four vertices), by identifying two suitable graphs $H_1$, $H_2$ along an edge, for $n\ge5$. No argument is printed for the remarks.
• References (p. 231, page image), the seven items listed above; the address and the received date.

Compiled scope

The paper is compiled at statement depth for the results Problem 915 consumes: Satz 1 (p. 223) with the Korollar (p. 226), the edge-disjoint reading's threshold, and the examples of pp. 228--229, the vertex-disjoint reading's unbounded excess, read on the page images, quoted above and paged at satz_1, korollar and examples_p228. Satz 2 (p. 229), which the problem page lists, is paged at satz_2. The structural results (Z) and (Y) and Satz 2 are recorded as statements read on the page images with their proofs read for structure. A filing observation, not a review verdict: the site and the filed Sørensen--Thomassen paper report the vertex-disjoint bound for $m\ge6$ ($k>5$), while the printed examples are stated "für ungerades $n\ge5$ (bzw. gerades $n\ge6$)", so the printed range includes $n=5$, where the excess is $m(\frac52-2)=\frac m2$. Nothing here is independently reviewed.

Bears on. #915: the site's key Ma73 and the source of both of the page's readings of "disjoint". Under the edge-disjoint reading, Satz 1 (printed p. 223, PDF p. 1), "Jeder endliche Graph $G$ mit $\kappa(G)>\frac n2(e(G)-1)-\frac12\sigma_n(G)$ und $e(G)\ge n$ enthält zwei Ecken $x$ und $y$ mit $\lambda(x,y;G)\ge n$", is the theorem the site records as "if a graph with $n$ vertices has $>\frac m2(n-1)-\frac12(e_0(G)+\cdots+e_{m-2}(G))$ edges then $G$ contains two vertices connected by $m$ edge-disjoint paths", and its Korollar (printed p. 226, PDF p. 4), "Für jeden Graphen $G$ mit $\kappa(G)>\frac n2(e(G)-1)$ gilt $\bar\lambda(G)\ge n$. Zu jeder ganzen Zahl $m\ge n\ge2$ existiert ein Graph $G$ mit $e(G)=m$, $\kappa(G)=\bigl[\frac n2(e(G)-1)\bigr]$ und $\bar\lambda(G)<n$", is the site's $\ell_m(n)=\lfloor\frac m2(n-1)+1\rfloor$ for every $m\ge2$; at the problem's parameters, a graph on $1+n(m-1)$ vertices with $1+n\binom m2$ edges has more than $\frac m2\cdot n(m-1)=n\binom m2$ edges and at least $m$ vertices, so the answer is yes for every $m\ge2$ under that reading, and the extremal graphs of the Korollar's proof at $e(G)=1+n(m-1)$, a universal vertex over an $(m-2)$-regular graph, have exactly $n\binom m2$ edges, one short (an arithmetic check made here). Under the vertex-disjoint reading, the examples of pp. 228--229 (PDF pp. 6--7) show "daß keine Konstante $c_n$ mit der Eigenschaft existiert, daß für jeden endlichen (2-fach zusammenhängenden) Graphen $G$ mit $\kappa(G)\ge\frac n2e(G)+c_n$ gilt $\bar\mu(G)\ge n$", for odd $n\ge5$ and even $n\ge6$: the site's "for all $m\ge6$ and any $C>0$, there exists an $n$ such that $k_m(n)>\frac m2n+C$", which the site and Sørensen--Thomassen report as disproving the conjectured $k_m(1+(m-1)n)=1+\binom m2n$ for every such $m$; the paper prints no statement about the conjecture itself under this reading and does not name Bollobás and Erdős. The paper settles nothing the page leaves open: the page's status is the site's label attached to the vertex-disjoint disproof, which is recorded through Sørensen and Thomassen's Theorem 4 and Leonard's counterexample, and this card records the edge-disjoint reading's status-defining theorem first-hand and adds the third first-hand vertex-disjoint disproof. Satz 2 (printed p. 229, PDF p. 7) does not decide the vertex-disjoint reading; it gives the conjectured conclusion only for graphs of girth at least $m+2$, $m\ge4$ (an arithmetic check made on its page). The problem page reads Satz 1, the Korollar and the examples on the page images at statement depth; no proof was checked.

Results.

• Satz 1 (p. 223): every finite graph $G$ with $e(G)\ge n$ and $\kappa(G)>\frac n2(e(G)-1)-\frac12\sigma_n(G)$ contains two vertices joined by $n$ edge-disjoint paths; by induction on the number of vertices through Menger's theorem (pp. 223--226).
• Korollar (p. 226): more than $\frac n2(e(G)-1)$ edges force $\bar\lambda(G)\ge n$, and for every $m\ge n\ge2$ some graph on $m$ vertices with $\bigl[\frac n2(m-1)\bigr]$ edges has $\bar\lambda(G)<n$; the exact edge-disjoint threshold.
• Examples (pp. 228--229): for odd $n\ge5$ and even $n\ge6$, graphs $\bar G$ with $\kappa(\bar G)=\frac n2(e(\bar G)-1)+m(\frac n2-2)$, or $+m(n-5)$, and $\bar\mu(\bar G)<n$, so no constant $c_n$ makes $\frac n2e(G)+c_n$ edges force two vertices joined by $n$ internally disjoint paths.
• Satz 2 (p. 229): for $n\ge4$, every finite graph $G$ with $\tau(G)\ge n+2$, $e(G)\ge n+1$ and $\kappa(G)>\frac n2(e(G)-(n-1))$ has $\bar\mu(G)\ge n$; through the auxiliary statement (X) and induction with Menger's theorem (pp. 229--231).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.