Abstract: We prove that Menger's theorem is valid for infinite graphs, in the following strong form: let and be two sets of vertices in a possibly infinite digraph. Then there exist a set of disjoint - paths, and a set of vertices separating from , such that consists of a choice of precisely one vertex from each path in . This settles an old conjecture of ErdH{o}s.
Recommendations
- Menger's Theorem for a Countable Source Set
- scientific article; zbMATH DE number 970819
- Sur une extension du théorème de Menger aux graphes infinis. (On an extension of Menger's theorem to infinite graphs)
- A minimax theorem for infinite graphs with ideal points
- Menger's theorem for infinite graphs with ends
Cites work
- scientific article; zbMATH DE number 3120162 (Why is no real title available?)
- scientific article; zbMATH DE number 3510341 (Why is no real title available?)
- scientific article; zbMATH DE number 1025912 (Why is no real title available?)
- scientific article; zbMATH DE number 970819 (Why is no real title available?)
- A General Criterion for the Existence of Transversals
- A counterexample to Aharoni's strongly maximal matching conjecture
- Another Criterion for Marriage in Denumerable Societies
- Ein Neuer Beweis Eines Mengerschen Satzes
- Greene-Kleitman's theorem for infinite posets
- Infinite graphs—A survey
- Infinite matching theory
- Injective choice functions for countable families
- Marriage in denumerable societies
- Matching theory
- Matchings in graphs of size \(\aleph_ 1\)
- Matchings in infinite graphs
- Menger's Theorem for a Countable Source Set
- Menger's theorem for countable graphs
- Menger's theorem for graphs containing no infinite paths
- Necessary and sufficient conditions for transversals of countable set systems
- On Dilworth's decomposition theorem
- On Representatives of Subsets
- Über Translationen und den Satz von Menger in unendlichen Graphen
Cited in
(51)- Enlarging vertex-flames in countable digraphs
- Graph-like continua, augmenting arcs, and Menger's theorem
- Menger sets in graphs
- Menger's theorem for matroids
- Minimal covers of infinite hypergraphs
- Edge-connectivity between edge-ends of infinite graphs
- Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
- Reducing the dichromatic number via cycle reversions in infinite digraphs
- Matroid intersection, base packing and base covering for infinite matroids
- 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
- Menger's theorem for infinite graphs with ends
- Menger's theorem for countable graphs
- The Lovász-Cherkassky theorem for locally finite graphs with ends
- Sur une extension du théorème de Menger aux graphes infinis. (On an extension of Menger's theorem to infinite graphs)
- The Menger-like property of the three-width of infinite graphs
- On the packing/covering conjecture of infinite matroids
- On the mixed connectivity conjecture of Beineke and Harary
- A formal approach to Menger's theorem
- A link between Menger's theorem and infinite Euler graphs
- Counterexamples to conjectures on strong maximality and minimality
- Edmonds' branching theorem in digraphs without forward-infinite paths
- A proof of Menger's Theorem by contraction
- Proof of Nash-Williams' intersection conjecture for countable matroids
- Countable Menger's theorem with finitary matroid constraints on the ingoing edges
- Strongly maximal antichains in posets
- A Riemann-Roch Theorem on Infinite Graphs
- scientific article; zbMATH DE number 6019705 (Why is no real title available?)
- Gallai-Milgram properties for infinite graphs
- Topological infinite gammoids, and a new Menger-type theorem for infinite graphs
- Locally finite graphs with ends: A topological approach. II: Applications
- A mechanized proof of the max-flow min-cut theorem for countable networks with applications to probability theory
- Buser's inequality on infinite graphs
- Counterexamples regarding linked and lean tree-decompositions of infinite graphs
- Busemann points of infinite graphs
- Disjoint dijoins for classes of dicuts in finite and infinite digraphs
- Tight infinite matrices
- Hindrance from a wasteful partial linkage
- Infinite gammoids
- The Lovász-Cherkassky theorem in infinite graphs
- A minimax theorem for infinite graphs with ideal points
- Menger's theorem
- scientific article; zbMATH DE number 3873367 (Why is no real title available?)
- On the intersection conjecture for infinite trees of matroids
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Vertex-flames in countable rooted digraphs preserving an Erdős-Menger separation for each vertex
- On the infinite Lucchesi–Younger conjecture I
- Greedoids from flames
- The Max-Flow Min-Cut theorem for countable networks
- On the intersection of infinite matroids
- The Lovász-Cherkassky theorem in countable graphs
- scientific article; zbMATH DE number 7535269 (Why is no real title available?)
This page was built for publication: Menger's theorem for infinite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016232)
