ABSTRACT
Although Erdõs' early focus was very strongly number-theoretic (61 of his first 64 papers were in number theory), he had early exposure (and success) in graph theory and combinatorics as well (e.g., his rediscovery with Szekeres in 1935 of Ramsey's theorem, see Chapter 2). This included several natural extensions to infinite graphs of some theorems known previously for finite graphs. Indeed, as a first-year undergraduate in 1931 in Konig's graph theory course, Erdõs proved an infinite generalization of Menger's theorem, which only appeared in 1936 at the end of Konig's classic book on graph theory.1 The result was this:
Given any two disjoint sets A and B of vertices in any graph, the minimum cardinality of an A-B separating set of vertices is equal to the maximum number of vertex-disjoint A-B paths.
