The Erdős-Menger conjecture for source/sink sets with disjoint closures

Reinhard Diestel

Erdős conjectured that, given an infinite graph G and vertex sets A, B ⊆ V (G), there exist a set P of disjoint A–B paths in G and an A–B separator X ‘on’ P, in the sense that X consists of a choice of one vertex from each path in P. We prove the conjecture for vertex sets A and B that have disjoint closures in the usual topology on graphs with ends. The result can be extended by allowing A, B and X to contain ends as well as vertices.

1. Introduction

The following conjecture of Erdős is one of the best known open problems in infinite graph theory:

Erdős-Menger Conjecture. For every graph G = (V, E) and any two sets A, B ⊆ V there is a set P of disjoint A–B paths in G and an A–B separator X consisting of a choice of one vertex from each of the paths in P.

The conjecture appears in print first in Nash-Williams’s 1967 survey [ 12 ] on infinite graphs, although it seems to be considerably older. It was proved by Aharoni for countable graphs [ 3 ], and by Aharoni et al. [ 2, 5 ] for bipartite graphs G with bipartition (A, B), and independently by Aharoni [ 1 ] and Polat [ 13 ] for graphs without infinite paths. The current state of the art, including further partial results by other authors, is described in Aharoni [ 4 ].

Our main result in this paper is the following:

Theorem 1.1. Every graph G satisfies the Erdős-Menger conjecture for all vertex sets A and B that have disjoint closures in |G|.

Here, |G| denotes the topological space usually associated with G and its ends, to be defined formally in Section 2. Expressed in this topological setting, the premise in Theorem 1.1 looks hardly stronger than A ∩ B = ∅, an assumption that we can make without loss of generality. While this may be taken as an indication of the strength of Theorem 1.1 compared with other known results, it should not lead one to believe that there remains only a little way to go: the additional assumption means that every infinite path in G can be separated from A or from B by a finite set of vertices, which remains a major assumption. For more discussion see Section 2, after the precise definitions of the terms involved.

In [ 8 ], the Erdős-Menger conjecture has been generalized to sets A and B that may include ends as well as vertices (in which case the paths in P may be rays or double rays between these ends or vertices, and the separator X may also contain ends from A or B), and proved in this more general form for countable G. Theorem 1.1, too, generalizes in this way:

Theorem 1.2. Every graph G = (V, E, Ω) satisfies the Erdős-Menger conjecture for all sets A, B ⊆ V ∪ Ω that have disjoint closures in |G|.

(Here, V and Ω denote the set of vertices and ends of G, respectively. The precise definitions of A–B paths and A–B separators for arbitrary sets A, B ⊆ V ∪ Ω are what one expects; see [ 8 ].)

Thus, formally, Theorem 1.1 is just a special case of Theorem 1.2. In order to concentrate on the original vertex case, however, we shall prove Theorem 1.1 directly and defer the more complicated proof of Theorem 1.2 to [ 6 ].

2. Terminology and basic tools

The basic terminology we use is that of [ 7 ] – except that most of our graphs will be infinite, and |G| will denote a certain topological space associated with a graph G, not its order. (For sets, we continue to use | | to denote cardinality.) Our graphs are simple and undirected, but the result we prove can easily be adapted to directed graphs.

An infinite path that has a first but no last vertex is a ray; a path with neither a first nor a last vertex is a double ray. The subrays of a ray are its tails. Any union of a ray R and infinitely many disjoint finite paths with their first vertex on R but otherwise disjoint from R is a comb with back R; the last vertices of those paths are the teeth of the comb. (Note that the paths may be trivial, ie. the teeth of a comb may lie on its back.)

Two rays in a graph G = (V, E) are equivalent if no finite set of vertices separates them in G. The corresponding equivalence classes of rays are the ends of G; the set of these ends is denoted by Ω = Ω(G), and G together with its ends is referred to as G = (V, E, Ω). (The grid, for example, has one end, the double ladder has two, and the binary tree has continuum many.) We shall endow our graphs G, complete with vertices, edges and ends, with a standard topology to be defined below. (When G is locally finite, this is its “Freudenthal compactification”.) This topological space will be denoted by |G|, and the closure in |G| of a subset X will be written as \overline{X}. See [ 9, 10 ] for more background on ends and this topology.

To define |G|, we start with G viewed as a 1-complex. Then every edge is homeomorphic to the real interval [ 0, 1 ], the basic open sets around an inner point being just the open intervals on the edge. The basic open neighbourhoods of a vertex x are the unions of half-open intervals [ x, z), one from every edge [ x, y] at x; note that we do not require local finiteness here.

For ω ^{∈} Ω and any finite set S ⊆ V, the graph G − S has exactly one component C = C(S, ω) that contains a tail of every ray in ω. We say that ω belongs to C. Write Ω(S, ω) for the set of all ends of G belonging to C, and E(S, ω) for the set of all edges of G between S and C. Now let |G| be the point set V ∪ Ω ∪ ⋃ E endowed with the topology generated by the open sets of the 1-complex G and all sets of the form

Ĉ(S, ω) := C(S, ω) ∪ Ω(S, ω) ∪ E′(S, ω) ,

where E′(S, ω) is any union of half-edges (x, y] ⊂ e, one for every e ^{∈} E(S, ω), with x ^{∈} e̊and y ^{∈} C. (So for each end ω, the sets Ĉ(S, ω) with S varying over the finite subsets of V are the basic open neighbourhoods of ω.) This is the standard topology on graphs with ends. With this topology, |G| is a Hausdorff space in which every ray, viewed as an arc, converges to the end that contains it. |G| is easily seen to be compact if and only if every vertex has finite degree.

A subgraph G′ = (V′, E′) of G will be viewed topologically as just the point set V′ ∪ ⋃ E′, without any ends. Then the closure \overline{G′} of this set in |G| may contain some ends of G, which should not be confused with ends of G′.

With precise definitions now available, let us take another look at what the assumption of \overline{A} ∩ \overline{B} = ∅ in Theorem 1.1 means for the relative position of the sets A and B (which we assume to be disjoint). One obvious way to ensure that \overline{A} ∩ \overline{B} = ∅ is to assume that some finite set of vertices separates A from B in G. For locally finite graphs (for which the Erdős-Menger conjecture is known), this assumption is indeed equivalent to \overline{A} ∩ \overline{B} = ∅. But in general it is much stronger, and the conjecture has long been known for this case (see Lemma 2.2 below). An example of \overline{A} ∩ \overline{B} = ∅ where A and B cannot be finitely separated is to take as A and B two distinct levels of vertices in the ℵ_{1}-regular tree.

We now list a few easy or well-known lemmas that we shall need in our proofs. Let us start with two observations about the Erdős-Menger conjecture itself. The first is that we may assume A and B to be disjoint:

Lemma 2.1. If G′ := G − (A ∩ B) satisfies the Erdős-Menger conjecture for A′ := A \ B and B′ := B \ A, then G satisfies the conjecture for A and B.

Proof. Let X′ be an A′–B′ separator on a set P′ of A′–B′ paths in G′. Then X′ ∪ (A ∩ B) is an A–B separator on the set P′ ∪ { (x) | x ^{∈} A ∩ B } of A–B paths in G, where (x) denotes the trivial path with vertex x. □

We shall also need the following special case of the Erdős-Menger conjecture, which can be reduced to finite graphs [ 11 ] and is covered by the results in [ 6 ].

Lemma 2.2. The Erdős-Menger conjecture holds for A and B in G if every set of disjoint A–B paths in G is finite.

Our next two lemmas are standard tools for infinite graphs.

Lemma 2.3. Let R ⊆ G be a ray, with end ω say, and X ⊆ V. Then ω ^{∈} \overline{X} if and only if G contains a comb with back R and teeth in X.

Proof. If ω /^{∈} \overline{X}, then ω has a neighbourhood Ĉ(S, ω) in |G| that avoids X. As R ^{∈} ω, R has a tail in C. Then all the infinitely many disjoint paths that start on this tail and end in X have to pass through the finite set S, a contradiction.

Conversely, if ω ^{∈} \overline{X} then every C = C(S, ω) meets both R and X, and we can construct the desired comb inductively by taking as S the (finite) union of the R–X paths already chosen, and finding a new R–X path in C. □

A proof of the following lemma can be found in [ 10 ].

Lemma 2.4. Assume that G is connected, and let U ⊆ V be an infinite set of vertices. Then G contains either a comb with |U| teeth in U or a subdivided star with |U| leaves in U. (Note that if U is uncountable then the latter holds.)

3. Proof of Theorem 1.1

The basic idea for the proof of Theorem 1.1 is to reduce the problem to rayless graphs, an early result of Aharoni [ 1 ]:

Lemma 3.1. (Aharoni 1983) The Erdős-Menger conjecture holds for all graphs containing no infinite path.

We shall eliminate the infinite paths in our given graph G in three steps. In the first two steps we eliminate the rays whose ends lie in \overline{A} and \overline{B}, respectively, and in the third step we eliminate any remaining rays.

The first step consists of the following reduction lemma applied with H := G and U := A and W := B.

Lemma 3.2. Let H = (V, E, Ω) be a graph, and let U, W ⊆ V be such that \overline{U} ∩ \overline{W} = ∅. Then there exist a subgraph H′ = (V′, E′, Ω′) of H containing W, and a set U′ ⊆ V′ with Ω′ ∩ \overline{U′} = ∅ (where the closure \overline{U′} is taken in |H′|), such that the Erdős-Menger conjecture holds for U and W in H if it holds for U′ and W in H′.

After this first step, it remains to prove the Erdős-Menger conjecture for A′ := U′ and B = W in G′ := H′. By Lemma 2.1, we may assume that A′ ∩ B = ∅. Since Ω′ ∩ \overline{A′} = ∅ in |G′| as a result of the first application of the lemma, we then have \overline{A′} ∩ \overline{B} = ∅. We may thus apply the lemma again with H := G′ and U := B and W := A′, to obtain a subgraph G′′ = (V′′, E′′, Ω′′) of G′ that contains A′ and a set U′ =: B′ such that Ω′′ ∩ \overline{B′} = ∅.

Note that also Ω′′ ∩ \overline{A′} = ∅ in |G′′|. For by Lemma 2.3 this is equivalent to the non-existence of a comb in G′′ with teeth in A′. As any such comb would also lie in G′, its existence would likewise imply Ω′ ∩ \overline{A′} ≠ ∅ in |G′|, a contradiction.

To this graph G′′ we then apply the following lemma as our third reduction step (setting H := G′′ and U := A′ and W := B′):

Lemma 3.3. Let H = (V, E, Ω) be a graph, and let U, W ⊆ V be such that Ω ∩ (\overline{U} ∪ \overline{W}) = ∅. Then H has a rayless subgraph H′ ⊆ H containing U ∪ W such that the Erdős-Menger conjecture for U and W holds in H if it does in H′.

Since the Erdős-Menger conjecture does hold in H′ by Lemma 3.1, this completes the proof of Theorem 1.1.

It remains to prove Lemmas 3.2 and 3.3.

Proof of Lemma 3.2. Our first aim is to construct a subgraph H^{∗} ⊆ H such that

(i) Ω ∩ \overline{U} ∩ \overline{H^{∗}} = ∅ in |H|; (ii) W ⊆ V (H^{∗}); (iii) for every component C of H − H^{∗}, its set S_{C} := N_{H}(C) of neighbours

in H^{∗} cannot be linked to U_{C} := U ∩ (V (C) ∪ S_{C}) by infinitely many disjoint paths in H_{C} := H [ V (C) ∪ S_{C} ].

Our desired graph H′ ⊆ H will be a supergraph of H^{∗}.

We define H^{∗} by transfinite ordinal recursion, as a limit H^{∗} = ⋂_{α⩽α^{∗}} H_{α} of a well-ordered descending family of subgraphs H_{α} indexed by ordinals. Let H_{0} := H, and for limit ordinals α > 0 let H_{α} := ⋂_{β<α} H_{β}. For successor ordinals α + 1 we first check whether Ω ∩ \overline{U} ∩ \overline{H_{α}} = ∅ in |H|, in which case we put α =: α^{∗} and terminate the recursion with H^{∗} = H_{α}. Otherwise pick ω_{α} ^{∈} Ω ∩ \overline{U} ∩ \overline{H_{α}}, and let S_{α} be a finite set of vertices such that Ĉ(S_{α}, ω_{α}) is a basic open neighbourhood of ω_{α} in |H| that does not meet W. (Such a set S_{α} exists, as \overline{U} ∩ \overline{W} = ∅ by assumption.) Put C_{α} := C(S_{α}, ω_{α}), and let H_{α+1} := H_{α} − C_{α}.

For any vertex v ^{∈} H −H^{∗} we record as α(v) := min{ α | v ^{∈} C_{α} } the ‘time it was deleted’. Note that, as ω_{α} ^{∈} \overline{H_{α}}, we have C_{α} ∩ H_{α} ≠ ∅ for every α, so the recursion terminates. Let us write C for the set of components of H − H^{∗}.

H^{∗} satisfies (i) because H^{∗} = H_{α^{∗}}, and (ii) by the choice of the S_{α} and C_{α}. To prove (iii), let a component C ^{∈} C be given. Suppose there is an infinite family P_{i} = s_{i} … u_{i} (i ^{∈} ℕ) of disjoint S_{C}–U_{C} paths in H_{C}. Let C′ ⊆ H_{C} be the graph obtained from C by adding for every i ^{∈} ℕ the vertex s_{i} and one s_{i}–C edge. Let us show that Lemma 2.4 yields a comb in C′ with its teeth in { s_{i} | i ^{∈} ℕ } ⊆ S_{C}. If not, then C′ contains an infinite subdivided star with its leaves in this set. As all the s_{i} have degree 1 in C′, the centre v of this star lies in C; let α := α(v). Then v ^{∈} C_{α} but S_{C} ⊆ V (H^{∗}) ⊆ V (H_{α+1}) ⊆ V (H − C_{α}), so the finite set S_{α} separates the star’s centre from its leaves, a contradiction. Hence C′ contains the desired comb; let ω ^{∈} Ω denote the end of its back. Then every basic open neighbourhood Ĉ(S, ω) of ω contains infinitely many s_{i}, and hence also infinitely many P_{i} and their endvertices in U. Therefore ω ^{∈} \overline{U} as well as ω ^{∈} \overline{S_{C}} ⊆ \overline{H^{∗}} in |H|, and thus Ω ∩ \overline{U} ∩ \overline{H^{∗}} ≠ ∅ contradicting (i). This completes the proof of (iii).

To expand H^{∗} to our desired subgraph H′, we now consider the components of H − H^{∗} separately. For every C ^{∈} C, there exist in H_{C} a finite set P_{C} of S_{C}–U_{C} paths and an S_{C}–U_{C} separator X_{C} on P_{C} (by (iii) and Lemma 2.2). Let D_{C} denote the set of all the components of H_{C} − X_{C} that meet U_{C}, and put D := ⋃_{C^{∈}C} D_{C}. Then let

H′ := H − ⋃ D and U′ := (U ∩ V′) ∪ ⋃_{C^{∈}C} X_{C} .

Let us show that Ω′ ∩ \overline{U′} = ∅ in |H′|. If not, then by Lemma 2.3 there is a comb K′ in H′ with teeth in U′; let R be its back. Using the paths in ⋃_{C^{∈}C} P_{C} (more precisely, their segments between X_{C} and U_{C}), we can extend K′ to a comb K in H with back R and teeth in U. Since every infinite subset of V (K) has the end of R in its closure, our condition (i) implies that K meets H^{∗} in only finitely many vertices. We may thus assume that K ⊆ C for some C ^{∈} C. As R is also the back of K′ ⊆ H′, we thus have R ⊆ C ∩ H′. But the finite set X_{C} separates C ∩ H′ from U_{C} in H_{C}, and hence the back of K from its teeth (a contradiction).

It remains to show that the Erdős-Menger conjecture holds for U and W in H if it holds for U′ and W in H′. Assume the latter, and let P′ be a set of disjoint U′–W paths in H′ with a U′–W separator X on it. Let P be obtained from P′ by appending to every P ^{∈} P′ whose first vertex u′ in U′ lies in U′ ∖ U, and hence in some X_{C}, the X_{C}–U_{C} segment of the path in P_{C} containing u′. These segments will be disjoint for different u′, because different C ^{∈} C are disjoint and the paths in P_{C} are disjoint for each C. (We remark that u′ may lie on X_{C} for several C if u′ ^{∈} H^{∗}, so the choice of C may not be unique.)

Thus, P is a set of disjoint U–W paths in H, and X consists of a choice of one vertex from each path in P. It remains to show that X separates U from W in H. So let Q be a U–W path in H. If Q ⊆ H′ then its first vertex lies in U ∩ V′ ⊆ U′, so Q links U′ to W in H′ and hence meets X. Suppose then that Q has a vertex in H − H′, and let z be its last such vertex. Then the component D of H − H′ containing z is an element of D_{C} for some C ^{∈} C, so N_{H}(D) = X_{C} ⊆ U′. As W ⊆ V′ and hence W ∩ D = ∅, the vertex z is not the last vertex of Q. But the vertex x following z on Q lies in H′, and hence in X_{C} ⊆ U′. So xQ joins U′ to W in H′ and hence meets X. □

For our proof of Lemma 3.3 we need the following lemma of Stein [ 14 ]. Let T be a finite set of vertices in a graph J. A T -path, for the purpose of this paper, is any path whose endvertices lie in T, whose inner vertices lie outside T, and which has at least one inner vertex. Paths P_{1}, …, P_{k} are said to be disjoint outside some given Q ⊆ J if P_{i} ∩ P_{j} ⊆ Q whenever i ≠ j.

Lemma 3.4. Let J be a graph, let T ⊆ V (J) be finite, and let k ^{∈} ℕ. Then J has a finite subgraph J′ containing T such that for every T -path Q = s … t in J that meets J − J′ there are k distinct T -paths from s to t in J′ that are disjoint outside Q.

A proof of Lemma 3.4 can be found in [ 8 ].

Proof of Lemma 3.3. As in the proof of Lemma 3.2, we start by constructing a subgraph H^{∗} ⊆ H. This time, we require that H^{∗} satisfy the following conditions:

(i) Ω ∩ \overline{H^{∗}} = ∅ in |H|; (ii) U ∪ W ⊆ V (H^{∗}); (iii) for every component C of H − H^{∗}, its set S_{C} := N_{H}(C) of neighbours

in H^{∗} is finite.

Again, our desired graph H′ ⊆ H will be a supergraph of H^{∗}.

We define H^{∗} recursively as before, putting H_{0} := H and H_{α} := ⋂_{β<α} H_{β} for limit ordinals α > 0. For successor ordinals α + 1 we check whether Ω ∩ \overline{H_{α}} = ∅ in |H|, in which case we put α =: α^{∗} and terminate the recursion with H^{∗} = H_{α}. Otherwise we pick ω_{α} ^{∈} Ω∩\overline{H_{α}} and a basic open neighbourhood Ĉ(S_{α}, ω_{α}) of ω_{α} in |H| that avoids U ∪ W, which exists as Ω ∩ (\overline{U} ∪ \overline{W}) = ∅ by assumption. We finally let C_{α} := C(S_{α}, ω_{α}) and H_{α+1} := H_{α} − C_{α}.

For vertices v ^{∈} H − H^{∗} put α(v) := min { α | v ^{∈} C_{α} }. Write C for the set of components of H − H^{∗}, and let H_{C} := H [ V (C) ∪ S_{C} ] for each C ^{∈} C.

As before, H^{∗} clearly satisfies (i) and (ii). To prove (iii), consider any component C ^{∈} C. If S_{C} is infinite, then H_{C} contains a comb with teeth in S_{C} (as before). But then the back of this comb has its end in \overline{H^{∗}}, contradicting (i). Therefore S_{C} is finite, as claimed.

To expand H^{∗} to our desired subgraph H′, we again consider the components of H − H^{∗} separately. For each C ^{∈} C, denote by H′_{C} the graph J′ which Lemma 3.4 returns on input J := H_{C}, T := S_{C}, and k := |S_{C}|. We then define

H′ := H^{∗} ∪ ⋃_{C^{∈}C} H′_{C} .

Let us show that H′ is rayless. Suppose there is a ray R in H′, say with end ω ^{∈} Ω. Since H′ contains from every component C of H − H^{∗} only the finite subgraph H′_{C} ∩ C, R must have infinitely many vertices in H^{∗}. But then ω lies in the closure in |H| of this set of vertices and hence in \overline{H^{∗}}, contrary to (i).

It remains to show that the Erdős-Menger conjecture holds for U and W in H if it does so in H′. Suppose there exist in H′ a set P of disjoint U–W paths and a U–W separator X on P. As H′ ⊆ H, it suffices to show that X also separates U from W in H. Suppose not, and let Q be a U–W path in H − X. As Q starts and ends in H^{∗}, and every segment of Q outside H^{∗} lies in some C ^{∈} C, we can find a sequence of internally disjoint segments sQt of Q, each with all its inner vertices in some C ^{∈} C (and at least one of these outside H′) and its endvertices s, t in S_{C}, such that the union of these segments contains Q − H′. Our aim is to replace each of these segments sQt ⊆ H_{C} with an S_{C}- path P_{st} from s to t in H′_{C} that avoids X: this will turn Q into a connected subgraph of H′ − X that contains both the starting vertex of Q in U and its endvertex in W, contradicting our assumption that X separates U from W in H′.

For our choice of P_{st}, Lemma 3.4 offers k = |S_{C}| different paths that are disjoint outside sQt. Since Q avoids X, we can thus find P_{st} as desired if we can show that X has fewer than k vertices in C. But every x ^{∈} X ∩ V (C) lies on a path P_{x} ^{∈} P that links U to W, and hence by (ii) has at least two vertices in S_{C}. As these P_{x} are disjoint for different x, X has at most |S_{C}|/2 < k vertices in C. □

References

1. R. Aharoni, Menger’s theorem for graphs containing no infinite paths, Eur. J. Comb. 4 (1983), 201–204.

2. R. Aharoni, König’s duality theorem for infinite bipartite graphs, J. Lond. Math. Soc. 29 (1984), 1–12.

3. R. Aharoni, Menger’s theorem for countable graphs, J. Comb. Theory B 43 (1987), 303–313.

4. R. Aharoni, A few remarks on a conjecture of Erdős on the infinite version of Menger’s theorem, in (R.L. Graham & J. Nešetřil, eds.): The Mathematics of Paul Erdős II, Springer-Verlag Heidelberg 1997.

5. R. Aharoni, C.St.J.A. Nash-Willliams & S. Shelah, A general criterion for the existence of transversals, Proc. Lond. Math. Soc. 47 (1983), 43–68.

6. H. Bruhn, R. Diestel & M. Stein, On the Erdős-Menger conjecture with ends, preprint 2003.

7. R. Diestel, Graph Theory (2nd edition), Springer-Verlag 2000.

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html

8. R. Diestel, The countable Erdős-Menger conjecture with ends, J. Comb. Theory B 87 (2003), 145–161.

9. R. Diestel, The cycle space of an infinite graph, Comb. Probab. Comput. (to appear).

10. R. Diestel & D. Kühn, Graph-theoretical versus topological ends of graphs, J. Comb. Theory B 87 (2003), 197–206.

11. D. König, Theorie der endlichen und unendlichen Graphen, Leipzig 1936.

12. C.St.J.A. Nash-Williams, Infinite graphs, a survey, J. Comb. Theory B 3 (1967), 286–301.

13. N. Polat, Sur une extension du théorème de Menger aux graphes infinis, Eur. J. Comb. 4 (1983), 359–365.

14. M. Stein, Die Erdős-Menger’sche Vermutung für abzählbare Graphen mit Enden, Diplomarbeit Universität Hamburg 2002.

Reinhard Diestel, Mathematisches Seminar der Universität Hamburg, Bundesstraße 55, D-20146 Hamburg, Germany; <diestel@math.uni-hamburg.de>.

Version 12 August 2004