Menger's theorem for infinite graphs

• 成果类型: Article
• 署名作者: Aharoni, Ron; Berger, Eli
• 署名单位: Technion Israel Institute of Technology; University of Haifa
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-008-0157-3
• 发表日期: 2009
• 页码: 1-62
• 关键词: matchings

摘要

We prove that Menger's theorem is valid for infinite graphs, in the following strong version: let A and B be two sets of vertices in a possibly infinite digraph. Then there exist a set P of disjoint A-B paths, and a set S of vertices separating A from B, such that S consists of a choice of precisely one vertex from each path in P. This settles an old conjecture of Erdos.