Menger's theorem for infinite graphs

896 views · Published 6 September 2016 · 51:48 · Indexed 29 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

We prove an old conjecture of Erdos, saying that Menger's theorem is valid also for infinite graphs, in the following strong form: given sets A and B of vertices in a graph (possibly directed, possibly infinite), there exists a family P of disjoint A-B paths, and an A-B separating set S, such that S consists of a choice of precisely one vertex from each path in P. The talk will describe the history of the problem and the main ideas of our proof. This is joint work with Ron Aharoni.

More from this channel