Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-05T21:40:25.287Z Has data issue: false hasContentIssue false
  • English
  • Français

Menger's Theorem for a Countable Source Set

Published online by Cambridge University Press:  12 September 2008

Ron Aharoni  and
Reinhard Diestel
Ron Aharoni
Affiliation:
Department of Mathematics, Technion, Haifa 32000, Israel
Reinhard Diestel
Affiliation:
Mathematical Institute, Oxford University, Oxford OX1 3LB, England
Get access Rights & Permissions [Opens in a new window]

Abstract

Paul Erdős has conjectured that Menger's theorem extends to infinite graphs in the following way: whenever A, B are two sets of vertices in an infinite graph, there exist a set of disjoint A−B paths and an A−B separator in this graph such that the separator consists of a choice of precisely one vertex from each of the paths. We prove this conjecture for graphs that contain a set of disjoint paths to B from all but countably many vertices of A. In particular, the conjecture is true when A is countable.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 2 , June 1994 , pp. 145 - 156
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aharoni, R. (1984) König's duality theorem for infinite bipartite graphs. J. London Math. Soc. 29 1–12.CrossRefGoogle Scholar
[2]Aharoni, R. (1987) Menger's theorem for countable graphs. J. Combin. Theory B 43 303–313.Google Scholar
[3]Aharoni, R. (1990) Linkability in countable-like webs. In: Hahn, G. et al. (eds.) Cycles and Rays, NATO ASI Ser. C, Kluwer Academic Publishers, Dordrecht.Google Scholar
[4]Aharoni, R. (1992) Infinite matching theory. In: Diestel, R. (ed.) Directions in Infinite Graph Theory and Combinatorics, Topics in Discrete Mathematics 3, North-Holland.Google Scholar
[5]König, D. (1936) Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesell-schaft, Leipzig (reprinted: Chelsea, New York 1950).Google Scholar