pith. sign in

arxiv: 2604.09117 · v1 · submitted 2026-04-10 · 🧮 math.CO

Menger's theorem for ends of digraphs

Florian Reich This is my paper

Pith reviewed 2026-05-10 17:32 UTC · model grok-4.3

classification 🧮 math.CO
keywords Menger's theoremends of digraphsdigraphsvertex separatorsinfinite graphsgraph connectivity
0
0 comments X

The pith

The maximum number of vertex-disjoint directed paths between two ends in a digraph equals the minimum size of a vertex separator between those ends.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Menger's theorem equates the largest number of internally vertex-disjoint paths between two vertex sets with the smallest vertex set that separates them. Polat previously extended the statement to ends in undirected graphs. This paper establishes the same min-max equality when all paths and separators are required to respect the directions of the edges. The equality is then used to give a concrete description of the combined degree of any end.

Core claim

In any digraph, for any two ends ω and τ, the maximum number of vertex-disjoint directed paths from ω to τ equals the minimum size of a vertex set whose removal separates ω from τ. This equality is applied to characterize the combined degree of an end.

What carries the argument

Ends of a digraph (equivalence classes of directed rays) together with directed A-B separators between such ends.

If this is right

  • The combined degree of an end equals the smallest size of a separator that splits the rays belonging to the end into two infinite classes.
  • Infinite digraphs admit a min-max theorem for end-to-end connectivity.
  • Structural results on infinite directed graphs can now be stated in terms of end-separators rather than path counts alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Many other min-max theorems originally proved for undirected graphs with ends may carry over to the directed case with little extra work.
  • The result supplies a foundation for flow or linkage problems in infinite directed networks whose sources and sinks lie at ends.
  • Countable digraphs become more amenable to algorithmic checks of end-connectivity via finite separator searches.

Load-bearing premise

The standard definitions of directed rays, ends, and vertex separators in digraphs permit a direct min-max relation without additional directed-specific obstructions.

What would settle it

A single digraph and pair of ends in which the largest collection of vertex-disjoint directed paths has a different size from the smallest vertex set separating those ends.

Figures

Figures reproduced from arXiv: 2604.09117 by Florian Reich.

Figure 1
Figure 1. Figure 1: There is no A–{ω2} separator of size 1 and there do not exist two disjoint A–{ω2} tracks. Therefore, we have to take into account a more general set of tracks: Let ⌊A⌋ be the union of A, the set of ends ω for which there exists an end a ∈ A with a ≤ ω and all A–in-dominating￾vertices: A vertex v is A–in-dominating if there exists a ray R in an end of A such that there are infinitely many R–v paths that int… view at source ↗
read the original abstract

Polat generalised Menger's theorem -- the maximum number of vertex-disjoint paths between two sets $A$ and $B$ equals the minimum size of an $A$-$B$ separator -- to ends of undirected graphs. In this paper we extend Menger's theorem to ends of digraphs. As an application, we characterise the combined degree of ends of digraphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript extends Polat's generalization of Menger's theorem from undirected graphs to digraphs. It establishes a min-max theorem stating that the maximum number of vertex-disjoint directed paths between two ends equals the minimum size of an A-B separator for those ends. The proof proceeds by a compactness argument that reduces the problem to the finite Menger theorem on finite subgraphs, followed by a limit argument. As an application, the authors characterize the combined degree of ends of digraphs by applying the main theorem with A and B taken as the two ends in question.

Significance. This is a natural and useful extension of a classical result to the directed infinite setting. The compactness reduction is a standard, reliable technique in infinite graph theory and appears to transfer without directed-specific obstructions. The immediate application to combined degrees illustrates the theorem's utility for studying connectivity properties at infinity in digraphs.

minor comments (3)
  1. The abstract and introduction would benefit from a short explicit statement of the precise definitions of directed ends and directed rays used in the paper, to make the extension from the undirected case immediately clear to readers.
  2. In the proof of the main theorem, the compactness argument is sketched at a high level; adding one or two sentences on how the finite separators are chosen uniformly across the directed subgraphs would improve readability.
  3. The application section on combined degree could include a brief remark on whether the characterization is sharp, perhaps by referencing a simple example digraph where the bound is attained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their supportive summary of our extension of Menger's theorem to ends of digraphs and for recommending minor revision. No specific major comments appear in the report provided.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation extends Polat's known min-max theorem for ends in undirected graphs to the directed setting via a compactness argument that reduces to the classical finite Menger theorem plus a standard limit argument on finite subgraphs. All load-bearing steps use externally cited results (Polat) and standard definitions of directed rays, ends, and separators; no self-citation is load-bearing, no parameter is fitted and renamed as a prediction, and no ansatz or uniqueness claim is smuggled in via prior author work. The application to combined degree follows directly from the theorem statement without redefinition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard combinatorial definitions and the known undirected case; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Menger's theorem holds for finite undirected graphs
    The base result is invoked as the starting point for the generalization.
  • domain assumption Ends of graphs are well-defined via equivalence classes of rays
    The paper assumes the usual definition of ends carries over to digraphs without modification.

pith-pipeline@v0.9.0 · 5338 in / 1387 out tokens · 81576 ms · 2026-05-10T17:32:09.207149+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    Aharoni and E

    R. Aharoni and E. Berger,Menger’s theorem for infinite graphs, Inventiones mathematicae176(2009), no. 1, 1–62

    work page 2009

  2. [2]

    Albrechtsen, M

    S. Albrechtsen, M. Pitz, and R. Schaut,Displaying prescribed sets of ends by linked tree-decompositions, arXiv preprint arXiv:2512.13457 (2025)

    work page arXiv 2025

  3. [3]

    L. F. Aurichi, P. M. J´ unior, and L. Real,Topological remarks on end and edge-end spaces, arXiv preprint arXiv:2404.17116 (2024)

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  4. [4]

    Bruhn, R

    H. Bruhn, R. Diestel, and M. Stein,Menger’s theorem for infinite graphs with ends, Journal of Graph Theory50(2005), no. 3, 199–211

    work page 2005

  5. [5]

    Craik, R

    S. Craik, R. Gray, V. Kilibarda, J. Mitchell, and N Ruˇ skuc,Ends of semigroups, Semigroup forum, 2016, pp. 330–346. 14 FLORIAN REICH

    work page 2016

  6. [6]

    Diestel,Graph theory, Springer (print edition); Reinhard Diestel (eBooks), 2024

    R. Diestel,Graph theory, Springer (print edition); Reinhard Diestel (eBooks), 2024

    work page 2024

  7. [7]

    Gollin and K

    J P. Gollin and K. Heuer,Characterising k-connected sets in infinite graphs, Journal of Combinatorial Theory, Series B157(2022), 451–499

    work page 2022

  8. [8]

    Gr¨ unwald,Ein neuer Beweis eines mengerschen Satzes, Journal of the London Mathematical Society 1(1938), no

    T. Gr¨ unwald,Ein neuer Beweis eines mengerschen Satzes, Journal of the London Mathematical Society 1(1938), no. 3, 188–192

    work page 1938

  9. [9]

    F. Gut, T. Krill, and F. Reich,Ubiquity of oriented rays, Journal of Graph Theory107(2024), no. 1, 200–211

    work page 2024

  10. [10]

    Halin,A note on Menger’s theorem for infinite locally finite graphs, Abhandlungen aus dem Mathem- atischen Seminar der Universit¨ at Hamburg40(1974), no

    R. Halin,A note on Menger’s theorem for infinite locally finite graphs, Abhandlungen aus dem Mathem- atischen Seminar der Universit¨ at Hamburg40(1974), no. 1, 111–114

    work page 1974

  11. [11]

    Hamann,A boundary for hyperbolic digraphs and semigroups, arXiv preprint arXiv:2403.06127 (2024)

    M. Hamann,A boundary for hyperbolic digraphs and semigroups, arXiv preprint arXiv:2403.06127 (2024)

    work page arXiv 2024

  12. [12]

    Hamann and K

    M. Hamann and K. Heuer,An end degree for digraphs, arXiv preprint arXiv:2412.01514 (2024)

    work page arXiv 2024

  13. [13]

    Hamann and K

    M. Hamann and K. Heuer,Infinite grids in digraphs, arXiv preprint arXiv:2412.03302 (2024)

    work page arXiv 2024

  14. [14]

    Koloschin, T

    M. Koloschin, T. Krill, and M. Pitz,End spaces and tree-decompositions, Journal of Combinatorial Theory, Series B161(2023), 147–179

    work page 2023

  15. [15]

    Kurkofka and M

    J. Kurkofka and M. Pitz,A representation theorem for end spaces of infinite graphs, arXiv preprint arXiv:2111.12670 (2021)

    work page arXiv 2021

  16. [16]

    Menger,Zur allgemeinen Kurventheorie, Fundamenta Mathematicae10(1927), no

    K. Menger,Zur allgemeinen Kurventheorie, Fundamenta Mathematicae10(1927), no. 1, 96–115

    work page 1927

  17. [17]

    C S. J. Nash-Williams,Infinite graphs—a survey, Journal of Combinatorial Theory3(1967), no. 3, 286– 301

    work page 1967

  18. [18]

    Pitz,Constructing Tree-Decompositions That Display All Topological Ends, Combinatorica42(2022), 763–769

    M. Pitz,Constructing Tree-Decompositions That Display All Topological Ends, Combinatorica42(2022), 763–769

    work page 2022

  19. [19]

    Polat,Aspects topologiques de la s´ eparation dans les graphes infinis

    N. Polat,Aspects topologiques de la s´ eparation dans les graphes infinis. I, Mathematische Zeitschrift165 (1979), 73–100

    work page 1979

  20. [20]

    Polat,A mengerian theorem for infinite graphs with ideal points, Journal of Combinatorial Theory, Series B51(1991), no

    N. Polat,A mengerian theorem for infinite graphs with ideal points, Journal of Combinatorial Theory, Series B51(1991), no. 2, 248–255

    work page 1991

  21. [21]

    Polat,Minimax theorems for infinite graphs with the ends as ideal points, Discrete Mathematics130 (1994), no

    N. Polat,Minimax theorems for infinite graphs with the ends as ideal points, Discrete Mathematics130 (1994), no. 1-3, 89–96

    work page 1994

  22. [22]

    Reich,Halin’s grid theorem for digraphs, to appear in Journal of Graph Theory (2024)

    F. Reich,Halin’s grid theorem for digraphs, to appear in Journal of Graph Theory (2024)

    work page 2024

  23. [23]

    Math.95(1970), 155–169

    B Zelinka,Uneigentliche Knotenpunkte eines Graphen, ˇCasopis Pˇ est. Math.95(1970), 155–169

    work page 1970

  24. [24]

    Zuther,Ends in digraphs, Discrete mathematics184(1998), no

    J. Zuther,Ends in digraphs, Discrete mathematics184(1998), no. 1-3, 225–244. Universit¨at Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Ham- burg, Germany Email address:florian.reich@uni-hamburg.de

    work page 1998