On the Erdős-Menger conjecture with ends

Henning Bruhn  Reinhard Diestel  Maya Stein

Abstract

A well-known conjecture of Erdős states that, given an infinite graph G and sets A, B ⊆ V (G), there exists a family of disjoint A–B paths P together with an A–B separator X consisting of a choice of one vertex from each path in P. There is a natural extension of this conjecture in which A, B and X may contain ends as well as vertices. We prove this extension for sets A and B that can be separated by countably many vertices or ends, and for sets A and B which have disjoint closures in the end topology of G.

1 Introduction

Erdős conjectured (see [11]) that Menger’s theorem should extend to infinite graphs as follows:

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.

There are several partial results [3]. In particular, Aharoni [2] proved the conjecture for countable graphs. In [4], this was extended as follows:

Theorem 1.1. [4] The Erdős-Menger conjecture holds for all graphs G and sets A, B ⊆ V that are separated in G by a countable set of vertices.

In particular, the conjecture holds whenever A is countable, regardless of the cardinality of G.

Another line of attack was taken in [7]. Again, an assumption is made that A and B are easy to separate. But this time, the notion of separation used is topological:

Theorem 1.2. [7] The Erdős-Menger conjecture holds for all graphs G and sets A, B ⊆ V whose closures in the topological space |G| consisting of G together with its ends are disjoint.

(See Section 2 for a formal definition of |G|, and some discussion of what the disjoint closures condition means for the relative position of A and B in G.)

Although Theorem 1.2 refers implicitly to the ends of G by its closure condition, the conclusion is the original one from Erdős’s conjecture, which makes no reference to ends. However, there is also a natural extension of the conjecture that does refer to ends. Here, the sets A and B may contain ends as well as vertices. The A–B paths in P can be either finite paths linking two vertices, or rays linking a vertex to an end, or double rays linking two ends. Similarly, the separator X may contain ends (that lie in A or B), thus blocking any ray belonging (= converging) to that end. This extension was proposed in [6], and found to be true for countable graphs under certain necessary restrictions for A and B.

In this paper, we extend both Theorems 1.1 and 1.2 to ends, in the spirit of [6]. Our extension of Theorem 1.2 will build on our extension of Theorem 1.1.

2 Definitions and statement of results

The basic terminology we use can be found in [5]. All the graphs in this paper are simple and undirected. As most of the graphs we deal with are infinite, we recall a few (standard) concepts for infinite graphs. Let G = (V, E) be a fixed infinite graph.

A 1-way infinite path is called a ray, a 2-way infinite path a double ray. The subrays of rays or double rays are their tails. The ends of G are the equivalence classes of rays under the following equivalence relation: two rays R_{1}, R_{2} in G are equivalent if no finite set of vertices separates them. As one easily observes, this condition holds if and only if there are infinitely many disjoint (finite) R_{1}–R_{2} paths. This in turn is equivalent to the existence of a ray that meets both R_{1} and R_{2} infinitely often. The set of ends of G is denoted by Ω = Ω(G), and we write G = (V, E, Ω) to refer to G together with its set of ends.

Paths in G can be finite paths (which contain at least one vertex), rays, double rays, or singleton sets {ω}, where ω is an end of G.

We will now define the standard topology on G together with its ends. We start by viewing G itself as a 1-complex. (Thus, the basic open neighbourhoods of an inner point of an edge are the open intervals on the edge containing that point, while the basic open neighbourhoods of a vertex v are the unions of halfopen intervals containing v, one from every edge at v.^{1} The point set of this 1-complex will again be denoted by G.) To extend this topology to the set G∪Ω, we have to define a neighbourhood basis for every end ω ∈ Ω. To do so, consider any finite set S ⊆ V. Then G − S has exactly one component C = C(S, ω) that contains a tail of every ray in ω. We say that ω belongs to C, and write \overline{C}(S, ω) for the component C together with all the ends of G belonging to C. As the basic open neighbourhoods of ω we now take all sets of the form

Ĉ(S, ω) := \overline{C}(S, ω) ∪ E′(S, ω),

where S is any finite subset of V and E′(S, ω) is any union of half-edges (z, y] ⊆ e, one for every edge e = xy with x ∈ S and y ∈ C (with z ∈ e̊).

Let |G| denote the topological space on G ∪ Ω thus defined. (When G is locally finite, |G| is a compact space known as the Freudenthal compactification of G; see [8, 9] for more.)

We write \overline{X} for the closure of a set X ⊆ |G| in |G|. For example, the set \overline{C}(S, ω) defined above is the closure in |G| of the set C(S, ω). Generally, the difference between a subgraph H and its closure \overline{H} is always a set of ends of G (possibly empty). These need not correspond to ends of H and should not be confused with them. For example, if G is the 1-way infinite ladder and H consists of all the rungs, then \overline{H} \ H consists of one point, the unique end ω of G. But H itself has no ends. Similarly, the subgraph H′ = G − E(H) of G is a double ray and thus has two ends, but \overline{H′} \ H′ = \{ω\} as before.

1Alternatively, we might fix for every edge [u, v] a homeomorphism with the real interval [0, 1] and take as basic open neighbourhoods for a vertex v only those unions of half-open edges [v, z) whose images in [0, 1] have the same length. This gives a different topology when vertices have infinite degrees, but since all relevant sequences of points will be sequences of vertices or of ends, the difference does not matter.

With precise definitions now available, let us take another look at what the assumption of \overline{A} ∩ \overline{B} = ∅ in Theorem 1.2 means for the relative position of the sets A and B (which we assume to be disjoint). Formally, the condition means that every ray in G can be separated by finitely many vertices from at least one of the sets A and B. An obvious way to ensure this, of course, is to assume that some finite set of vertices separates A from B. But this is much stronger (except when G is locally finite), and the conjecture has long been known for this case. A more typical example of \overline{A} ∩ \overline{B} = ∅ is to take as A and B two distinct levels of vertices in the κ-regular tree (for κ any infinite cardinal), in which case G contains κ disjoint A–B paths.

The closure of an infinite path P contains one or two ends of G. (Even if P is a double ray, its closure may contain only one end, as in the ladder example above.) We will often consider such an end as the first or last point of P, and when we say that two paths are disjoint then these points too shall be distinct. (The first and last point of a path P = {ω}, of course, is ω.) For A, B ⊆ V ∪ Ω, a path is an A–B path if its first but no other point lies in A and its last but no other point lies in B.

A set X ⊆ V ∪ Ω is an A–B separator in a subspace T ⊆ |G| if every path P in T with its first point in A and its last point in B satisfies \overline{P} ∩ X ≠ ∅. (We express this informally by saying that “P meets X”, though strictly speaking we shall mean \overline{P} rather than just P.) We say that a set Y ⊆ V ∪ Ω lies on a set P of disjoint A–B paths if Y consists of a choice of exactly one vertex or end from every path in P. We say that G satisfies the Erdős-Menger conjecture for A and B, or that the Erdős-Menger conjecture holds for G, A, B, if |G| contains a set P of disjoint A–B paths and an A–B separator on P. (Thus, officially, we always refer to the ends version of the conjecture. But this is compatible with the traditional terminology: if neither A nor B contains an end then neither can any A–B path, so the conjecture with ends automatically defaults to the original conjecture in this case.)

The union of a ray R and infinitely many disjoint paths starting on R but otherwise disjoint from R is a comb with spine R. The last points (vertices or ends) of those paths are the teeth of the comb. We will frequently use the following simple lemma:

Lemma 2.1. In the graph G = (V, E, Ω) let R be a ray of an end ω, and let X ⊆ V ∪ Ω such that ω ∉ X. Then ω ∈ \overline{X} if and only if G contains a comb with spine R and teeth in X.

We can now state our two main results. First, our extension of Theorem 1.1:

Theorem 2.2. Let G = (V, E, Ω) be a graph, let A, B ⊆ V ∪ Ω satisfy A ∩ \overline{B} = ∅ = \overline{A} ∩ B, and suppose that there exists a countable A–B separator X ⊆ V ∪ Ω in G. Then G satisfies the Erdős-Menger conjecture for A and B.

In particular, the ends version of the Erdős-Menger conjecture is true whenever A is countable. We remark that the condition A ∩ \overline{B} = ∅ = \overline{A} ∩ B is really necessary [6]; so Theorem 2.2 is best possible in this respect. If neither A nor B contains an end, the condition reduces to A ∩ B = ∅, which we may always assume without loss of generality; thus, Theorem 2.2 implies Theorem 1.1.

Our second main result, whose proof builds on Theorem 2.2, extends Theorem 1.2 fully to its natural topological setting:

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

Let us complete this section with an outline of the proofs to come, and of how the paper is organized.

The proof of Theorem 2.2 will occupy us for the next two sections. It runs roughly as follows. Most of the proof – all of Section 3 – will be spent on transferring our problem to an equivalent problem in which G is replaced with a suitable minor and A and B consist of vertices only. In this new situation, the countable A–B separator X – which likewise may be assumed to consist of vertices only – divides G into two parts: one between X and A (including both) and the rest (which includes B). We now apply Theorem 1.1 to obtain an A–X separator Y on a system of disjoint A–X paths in the first part. Note that Y is again countable, and it separates A from B in G. Repeating the same procedure for the part of G between Y and B yields a system of Y –B paths with a separator Z on it, which again separates A from B. These paths can be concatenated with the A–Y segments of the first, to give a system of disjoint A– B paths (with the A–B separator Z on it). It remains to transfer this solution back to the original sets A, B containing ends, in the original graph G.

In Section 5 we prove Theorem 2.3. Employing techniques developed in Section 3 and in [7], we will eliminate all ends in the closures of A and B. Then the remaining ends can be discarded as well. In this way, the problem is reduced to a rayless graph, for which the Erdős-Menger conjecture is known to hold:

Theorem 2.4 (Aharoni [1], Polat [12]). The Erdős-Menger conjecture holds for rayless graphs.

3 The reduction lemma

In this section we develop further some techniques from [6] designed to reduce the ends versions of the Erdős-Menger conjecture to the related vertex versions. Observe that in the finite Menger theorem we can ignore all the vertices in A∩B and work with the graph G − (A ∩ B) instead. In an infinite graph, however, we have to take care that no end in A ∪ B is destroyed or split when the vertices of A ∩ B are deleted from G.

Lemma 3.1. Let G = (V, E, Ω) be a graph, and let A, B ⊆ V ∪ Ω satisfy

A ∩ (\overline{B} \ B) = ∅ = (\overline{A} \ A) ∩ B.

Then for the graph G′ := G − (A ∩ B ∩ V) there are sets A′, B′ ⊆ V (G′) ∪ Ω(G′) satisfying

(i) |A′| ≤ |A|;

(ii) if A ⊆ V then A′ ⊆ A, and if B ⊆ V then B′ ⊆ B; (iii) A′ ∩ \overline{B′} = ∅ = \overline{A′} ∩ B′;

(iv) if G′ satisfies the Erdős-Menger conjecture for A′ and B′, then G satisfies it for A and B.

Proof. Put A′ := A \ B and B′ := B \ A, both of which are subsets of |G|. Consider a ray R of an end α in A′ or B′, say in A′. Then R has a tail in G′. Indeed, if not then there are vertices of A ∩ B ∩ V ⊆ B in every neighbourhood of α ∈ A\B. Consequently, α ∈ A∩(\overline{B} \B), which is a contradiction. Similarly, two rays R_{1}, R_{2} in G′ of which R_{1} is a ray of an end ω ∈ A′ ∪ B′ are equivalent in G′ if and only if they are equivalent in G. Indeed, if R_{1} and R_{2} are equivalent in G then there is a ray R_{3} ∈ ω that meets both of R_{1} and R_{2} infinitely often. Now R_{3} has a tail in G′, showing that R_{1} and R_{2} are also equivalent in G′.

Thus, mapping every end of G in A′ ∪ B′ to the unique end of G′ that contains tails of its rays defines a bijection between the ends in A′ ∪ B′ and certain ends in G′. Using this bijection (and a slight abuse of notation) we may view A′ and B′ also as subsets of V (G′) ∪ Ω(G′). Clearly, A′ ∩ B′ is empty and hence (iii) is satisfied. Also, (i) and (ii) are trivial.

For (iv), let X′ be an A′–B′ separator on a set of disjoint A′–B′ paths P′ in G′. Adding to P′ the trivial paths {x} for all x ∈ A ∩ B yields a set P of disjoint A–B paths on the A–B separator X := X′ ∪ (A ∩ B).

Later on, in Lemma 3.5, we shall need a family of disjoint subgraphs of G (with certain properties) such that every end of A lies in the closure of one of these subgraphs. Such a family cannot always be found. But our next lemma finds instead a family of subgraphs such that the ends of A not contained in their closures form a set I that can be ignored: those ends will automatically be separated from B by any (A \ I)–B separator on a set of disjoint A–B paths.

Lemma 3.2. Let G = (V, E, Ω) be a graph, and let A, B ⊆ V ∪ Ω be such that A∩\overline{B} = ∅ = \overline{A}∩B. Then for every set A_{Ω} ⊆ A∩Ω there exist a set I ⊆ A_{Ω}, an ordinal μ^{∗}, and families (G_{μ})_{μ<μ^{∗}} and (S_{μ})_{μ<μ^{∗}} such that, for every μ < μ^{∗}, the graph G_{μ} − S_{μ} is a component of G − S_{μ} with S_{μ} as its finite set of neighbours, and

(i) \overline{G_{μ} − S_{μ}} ∩ B = ∅;

(ii) if G_{μ} ≠ ∅ then \overline{G_{μ}} ∩ A_{Ω} ≠ ∅;

(iii) V (G_{ν} ∩ G_{μ}) ⊆ S_{ν} ∩ S_{μ} for all ν < μ.

Moreover,

(iv) for every end α ∈ A_{Ω} \ I there is a μ < μ^{∗} with α ∈ \overline{G_{μ}};

(v) every (A \ I)–B separator on a set of disjoint (A \ I)–B paths is also an A–B separator.

Proof. We construct the families (G_{μ})_{μ<μ^{∗}} and (S_{μ})_{μ<μ^{∗}} and a transfinite sequence I_{0} ⊆ I_{1} ⊆ … ⊆ A_{Ω} recursively. The sets I_{μ} (μ < μ^{∗}) will serve as precursors to I. To simplify notation, we write C_{μ} := G_{μ} − S_{μ} for every μ. For the construction, we will in addition to (i)–(iii) require for every μ that

(vi) I_{μ} ∩ \overline{G_{ν}} = ∅ for all ν ≤ μ.

We start by setting I_{0}, G_{0}, S_{0} := ∅. Consider the least ordinal μ > 0 such that the above sets are already defined for all λ < μ. If μ is a limit, we set

I_{μ} := ⋃_{λ<μ} I_{λ}

and G_{μ}, S_{μ} := ∅. This choice clearly satisfies (i)–(iii) and (vi).

Suppose now that μ is a successor, μ = λ + 1 say. If every end in A_{Ω} \ I_{λ} lies in some \overline{G_{ν}} with ν < μ, we set μ^{∗} := μ and terminate the recursion. So suppose there is an end α ∈ A_{Ω} \ I_{λ} that lies in no earlier \overline{G_{ν}}. Then, if possible, choose a finite vertex set S such that C(S, α) avoids all G_{ν} with ν < μ.

Such a choice of S is impossible if and only if

for every finite S ⊆ V there is a ν < μ with C(S, α) ∩ G_{ν} ≠ ∅.  (1)

In this case we choose to ignore α, i.e. set I_{μ} := I_{λ} ∪{α} and G_{μ}, S_{μ} := ∅. Again the requirements (i)–(iii) are clearly met, while (vi) holds by the choice of α.

Now suppose we can find S as desired. As A ∩ \overline{B} = ∅, we can also find a basic open neighbourhood Ĉ(S′, α) of α in |G| that is disjoint from B. We now define S_{μ} as the set of neighbours of C(S ∪ S′, α) and G_{μ} := G[S_{μ} ∪ C(S_{μ}, α)]. Then (i) holds since S_{μ} ⊇ S′, while (ii) holds as α ∈ \overline{G_{μ}}. To see (iii), first note that

G_{ν} ∩ C_{μ} = ∅ for all ν < μ

by the choice of S. So, all we have to show is that G_{ν} ∩ S_{μ} ⊆ S_{ν}. Consider a vertex v ∈ G_{ν} ∩ S_{μ}. Since S_{μ} is the set of neighbours of C_{μ}, there is a vertex w ∈ C_{μ} adjacent to v. As noted above, w ∉ G_{ν}. So v is a vertex in G_{ν} = C_{ν} ∪ N(C_{ν}) with a neighbour outside G_{ν}, implying v ∉ C_{ν} and hence v ∈ S_{ν}, as desired.

Let us finally set I_{μ} := I_{λ} and verify (vi). We only need to show that I_{μ} ∩ \overline{G_{μ}} = ∅. Suppose that intersection contains an end α′. Let μ′ < μ be minimal such that α′ ∈ I_{μ′}. Then (1) should have been satisfied for μ′ and α′, but fails with S := S_{μ} as C(S_{μ}, α′) = C_{μ}, a contradiction.

Having defined I_{μ}, G_{μ} and S_{μ} for all μ < μ^{∗} so that (i)–(iii) and (vi) are satisfied, we put

I := ⋃_{μ<μ^{∗}} I_{μ}.

Together with the definition of μ^{∗} this implies (iv). Observe that from (vi) we obtain I ∩ \overline{G_{μ}} = ∅ for all μ < μ^{∗}.

To establish (v) let P be a system of disjoint (A \ I)–B paths and X an (A \ I)–B separator on P. Now suppose that X is not an A–B separator in |G|, i.e. there is a path Q from A to B that avoids X. By turning Q into a path Q̃ from A \ I to B that avoids X, we will obtain a contradiction.

We may assume that Q starts at an end α ∈ I. Let μ be the step at which α was added to I, i.e. let μ be minimal with α ∈ I_{μ}. Choose a finite vertex set S such that \overline{C}(S, α) is disjoint from B (this is possible, as A ∩ \overline{B} = ∅). Then any path of P that meets C(S, α) must pass through S. Hence only finitely many paths of P can meet C(S, α), and so X_{α} := X ∩ \overline{C}(S, α) is also finite.

Conditions (iii) and (iv) ensure that every end in X_{α} lies in exactly one \overline{C_{λ}}; let {λ_{1}, …, λ_{m}} be the set of these λ. Then for

S′ := S ∪ (X_{α} ∩ V) ∪ ⋃_{i=0}^{m} S_{λ_{i}}

we have

\overline{C}(S′, α) ∩ X = ∅.

Now, all we need is a point of A \ I that lies in \overline{C}(S′, α) (and thus can be used to change Q into the desired path). Indeed, if there is an ordinal λ < μ such that G_{λ} ≠ ∅ and

C_{λ} ⊆ C(S′, α),  (2)

we can complete the proof as follows. By (ii) for λ there will be an end α′ ∈ A in \overline{C_{λ}} ⊆ \overline{C}(S′, α). Since I ∩ \overline{G_{λ}} = ∅, we have α′ ∈ A \ I. Take an α′–Q path P in \overline{C}(S′, α) with last vertex x, say. Then P avoids X, and hence so does the path Q̃ := P xQ. Thus, Q̃ is as desired.

So suppose there is no ordinal λ < μ satisfying (2). Then for all λ < μ we have either C_{λ} ∩ C(S′, α) = ∅ or C_{λ} ∩ S′ ≠ ∅. As all the C_{λ} are disjoint by (iii), only finitely many of them meet S′; let λ_{m+1}, …, λ_{n} be the corresponding ordinals. Then

S′′ := S′ ∪ ⋃_{i=m+1}^{n} S_{λ_{i}}

satisfies C(S′′, α) ∩ C_{λ} = ∅ for all λ < μ.

However, G_{λ} ∩ C(S′′, α) cannot be empty for all λ < μ, as this would contradict (1) for step μ with S := S′′. So there exists an ordinal λ < μ with S_{λ} ∩ C(S′′, α) ≠ ∅. A vertex v in this intersection must have a neighbour in C_{λ}, which then also lies in S′ ∪ C(S′, α) because C(S′′, α) ⊆ C(S′, α). Thus,

(S′ ∪ C(S′, α)) ∩ C_{λ} ≠ ∅.

Since C_{λ} ⊈ C(S′, α) by assumption, this implies that C_{λ} meets S′. But then λ ∈ {λ_{m+1}, …, λ_{n}} and hence S_{λ} ⊆ S′′, contradicting the fact that v lies in both S_{λ} and C(S′′, α).

For our end-to-vertex reduction we need two more lemmas.

Lemma 3.3. [6] Let H be a subgraph of a graph G, let S ⊆ V (H) be finite, and let T ⊆ V (H) ∪ Ω(G) be such that T ⊆ \overline{H}. Then \overline{H} contains a set P of disjoint S–T -paths and an S–T -separator (in \overline{H}) on P.

For a set T of vertices in a graph H, a T -path is a path that meets T only in its first and last vertex. A set of paths will be called disjoint outside a given subgraph Q ⊆ H if distinct paths meet only in Q.

Lemma 3.4. [13, 6] Let H be a graph, T ⊆ V (H) finite, and k ∈ ℕ. Then H has a subgraph H′ containing T such that for every T -path Q = s … t in H meeting H − H′ there are k distinct T -paths from s to t in H′ that are disjoint outside Q.

Our next lemma allows us to replace the set A ⊆ V ∪ Ω in Theorem 2.2 with a set A′ consisting only of vertices.

Lemma 3.5. Let G = (V, E, Ω) be a graph, and let A, B ⊆ V ∪ Ω be such that A ∩ \overline{B} = ∅ = \overline{A} ∩ B. Then there are a minor G′ = (V′, E′, Ω′) of G and sets A′ ⊆ V′, B′ ⊆ V′ ∪ Ω′ satisfying

(i) |A′| ≤ |A|;

(ii) if B ⊆ V then B′ ⊆ B;

(iii) A′ ∩ \overline{B′} = ∅ = \overline{A′} ∩ B′;

(iv) G satisfies the Erdős-Menger-conjecture for A and B if G′ satisfies it for A′ and B′.

Proof. Applying Lemma 3.2 with A_{Ω} := A ∩ Ω we obtain an ordinal μ^{∗}, subgraphs G_{μ}, finite vertex sets S_{μ} and a set of ends I ⊆ A. Our aim is to change G into G′ by deleting and contracting certain connected subgraphs of our graphs G_{μ} − S_{μ}. By Lemma 3.2 (iii) we shall be able to do this independently for the various G_{μ}: for each μ < μ^{∗} separately, we shall find in G_{μ} − S_{μ} a set D_{1}(μ) of connected subgraphs to be deleted, and another set D_{2}(μ) of connected subgraphs that will be contracted.

Fix μ < μ^{∗}. If G_{μ} is empty we let D_{1}(μ) = D_{2}(μ) = ∅. Assume now that G_{μ} ≠ ∅. Put A_{μ} := A ∩ \overline{G_{μ}}. Applying Lemma 3.3 to H = G_{μ} we find in \overline{G_{μ}} a finite set P of disjoint S_{μ}–A_{μ} paths and an S_{μ}–A_{μ} separator X_{μ} on P. We write X_{μ} = U_{μ} ∪ O_{μ}, where U_{μ} = X_{μ} ∩ V and O_{μ} = X_{μ} ∩ Ω, both of which are finite since |X_{μ}| ≤ |P| ≤ |S_{μ}|. Moreover,

U_{μ} separates S_{μ} from A_{μ} \ O_{μ} in G.  (3)

Indeed, every S_{μ}–(A_{μ} \ O_{μ}) path in G lies in \overline{G_{μ}} and hence meets X_{μ}, and since it cannot meet O_{μ} unless it ends there, it meets X_{μ} in U_{μ}.

We define D_{1}(μ) as the set of all the components D of G − U_{μ} whose closure \overline{D} meets A_{μ} \ O_{μ}. By (3), these components satisfy D ⊆ G_{μ} − S_{μ}, and their neighbourhood N(D) ⊆ U_{μ} in G is finite. In addition,

\overline{D} ∩ O_{μ} = ∅ for all D ∈ D_{1}(μ).  (4)

For if α ∈ \overline{D} ∩ O_{μ}, say, and P is the S_{μ}–A_{μ} path in P that ends in α, then P has a tail in D. Since P does not meet U_{μ} ⊇ N(D), this implies P ⊆ \overline{D}. Consequently, S_{μ} ∩ D is not empty as it contains at least the first vertex of P. This contradicts D ⊆ G_{μ} − S_{μ}.

Put

H_{μ} := G_{μ} − ⋃ D_{1}(μ).

Note that, as every v ∈ U_{μ} lies on a path in P,

G_{μ} contains a set of disjoint H_{μ}–A_{μ} paths whose set of first points

is U_{μ}. (5)

By (3) and the definition of H_{μ}, we have \overline{H_{μ}} ∩ A ⊆ U_{μ} ∪ O_{μ} = X_{μ}. Since O_{μ} is finite, we can extend U_{μ} ∪ S_{μ} to a finite set T_{μ} ⊆ V (H_{μ}) that separates the ends in O_{μ} pairwise in G. Let H′_{μ} be the finite subgraph of H_{μ} containing T_{μ} which Lemma 3.4 provides for k := |S_{μ}| + 1, and for each α ∈ O_{μ} let D_{α} be the component of G − H′_{μ} to which α belongs. Finally, we conclude our definitions for μ by setting D_{2}(μ) := {D_{α} | α ∈ O_{μ}}.

Define for i = 1, 2

D_{i} := ⋃_{μ<μ^{∗}} D_{i}(μ).

Observe that, by Lemma 3.2 (iii) and since their neighbourhoods in G are finite, the elements of D_{1} ∪ D_{2} have pairwise disjoint closures.

Before we can define G′, we first have to introduce a graph G̃ = (Ṽ , Ẽ, Ω̃) from which we will obtain G′ by deleting certain vertices. Let G̃ be obtained from G − ⋃ D_{1} by contracting every D_{α} ∈ D_{2} to a single vertex a_{α}, and put

A^{∗} := {a_{α} | D_{α} ∈ D_{2}}.

Then for Z := ⋃ D_{1} ∪ ⋃ D_{2} we have

G − Z = G ∩ G̃ = G̃ − A^{∗}.

By Lemma 3.2 (iii) and by (3), the union of the sets of paths in (5) for all μ < μ^{∗} is a set of disjoint paths. Thus, for U := ⋃_{μ<μ^{∗}} U_{μ}

there is a set of disjoint U–A paths whose set of first points is U, and whose paths meet G̃ only in U.

(6)

An important property of G̃ is that the ends of G in B ∩ Ω correspond closely to ends of G̃. To establish this correspondence formally, we begin with the following observation:

Every ray of an end β ∈ B has a tail in G − Z.  (7)

To see this, recall that all the D ∈ D_{1} ∪ D_{2} have pairwise disjoint closures, and that each of them is a connected subgraph of G whose closure contains an end or a vertex of A. Hence, a ray R of β meets only finitely many D ∈ D_{1} ∪ D_{2}, as we could otherwise find infinitely many disjoint R–A paths, giving \overline{A} ∩ B ≠ ∅ by Lemma 2.1 – a contradiction. Also, R meets every D ∈ D_{1} ∪ D_{2} only finitely often. Indeed, D lies in G_{μ} for some μ < μ^{∗} and is thus, by Lemma 3.2 (i), separated from β by its finite set of neighbours N(D). This establishes (7).

Let R_{1}, R_{2} be two rays in G ∩ G̃, and assume that the end of R_{1} lies in B. Then R_{1} and R_{2} are equivalent in G if and only if they are equivalent in G̃.

(8)

To prove (8), suppose first that R_{1}, R_{2} are equivalent in G, i.e. belong to the same end β ∈ B. Then there is a ray R_{3} that meets both R_{1} and R_{2} infinitely often, and hence ends in β. By (7), R_{3} has a tail in G − Z = G̃ − A^{∗}, showing that R_{1} and R_{2} are equivalent also in G̃.

Conversely, if R_{1} and R_{2} are joined in G̃ by infinitely many disjoint paths, we can replace any vertices a_{α} ∈ Ṽ \ V = A^{∗} on these paths by finite paths in D_{α} to obtain infinitely many disjoint R_{1}–R_{2} paths in G. This completes the proof of (8).

We can now define our correspondence between the ends in B and certain ends of G̃. For every end β ∈ B there is by (7) an end β′ ∈ Ω̃ such that β ∩ β′ ≠ ∅. By (8), this end β′ is unique and the map β ↦ β′ is injective. Moreover,

B̃ := (B ∩ V) ∪ {β′ | β ∈ B ∩ Ω} ⊆ Ṽ ∪ Ω̃

by Lemma 3.2 (i). For each μ < μ^{∗}, let

Ã_{μ} := U_{μ} ∪ {a_{α} | α ∈ O_{μ}},

if G_{μ} ≠ ∅; if G_{μ} = ∅, put A_{μ}, Ã_{μ} := ∅. Then let

Ã := (A \ ( ⋃_{μ<μ^{∗}} A_{μ} ∪ I)) ∪ ⋃_{μ<μ^{∗}} Ã_{μ},

which is a subset of Ṽ by Lemma 3.2 (iii),(iv). Finally, let

G′ := G̃ − (Ã ∩ B̃).

To show the assertions (i)–(iv), we will apply Lemma 3.1 to the graph G̃ and the sets Ã and B̃.

So, let us show that

(\overline{Ã} \ Ã) ∩ B̃ = ∅ = Ã ∩ (\overline{B̃} \ B̃)

(with closures taken in |G̃|). We trivially have Ã ∩ (\overline{B̃} \ B̃) = ∅ because Ã ⊆ Ṽ. To prove that (\overline{Ã} \ Ã) ∩ B̃ = ∅, consider an end β′ ∈ B̃. The corresponding end β ∈ B has a neighbourhood C := Ĉ(S, β) in |G| that avoids A. By (6), and since S is finite, the intersection C ∩ U =: U_{C} is finite. Also, as in the proof of (7), C may meet only finitely many D_{α} ∈ D_{2}. Denote by O_{C} the set of the corresponding a_{α} ∈ G̃. Adding to S \ Z the sets U_{C} and O_{C} then yields a finite set S′ ⊆ Ṽ such that the neighbourhood Ĉ′(S′, β′) in |G̃| even avoids Ã.

Thus, Lemma 3.1 is applicable and yields sets A′ ⊆ V′ and B′ ⊆ V′ ∪ Ω′ satisfying (iii). For (i) use Lemma 3.1 (i), and observe that |Ã| ≤ |A|. (Indeed, Ã is comprised of two sets, one of which is contained in A. The other set, ⋃_{μ<μ^{∗}} Ã_{μ}, has cardinality at most |A| by (6).) Assertion (ii) follows from the definition of B̃ and Lemma 3.1 (ii).

We now prove assertion (iv) of the lemma. Suppose G′ satisfies the Erdős-Menger conjecture for A′ and B′. Then, by Lemma 3.1, there is also in G̃ a set P̃ of disjoint Ã–B̃ paths and an Ã–B̃ separator X̃ on P̃. In order to turn P̃ into a set P := {P | P̃ ∈ P̃} of disjoint A–B paths in G, consider any P̃ ∈ P̃. If the first point a of P̃ lies in A we leave P̃ unchanged, i.e. set P := P̃. If a ∈ Ã \ (A ∪ A^{∗}), then a ∈ U_{μ} for some μ < μ^{∗}, and we let P be the union of P̃ with an A_{μ}–U_{μ} path in G_{μ} that ends in a; this can be done disjointly for different P̃ ∈ P̃ if we use the paths from (6). Moreover, the A_{μ}–H_{μ} path concatenated with P̃ in this way has only its last vertex in G̃, so it will not meet any other vertices on P̃. Finally if a = a_{α} ∈ A^{∗}, we let P be obtained from P̃ by replacing a with a path in D_{α} that starts at the end α and ends at the vertex of D_{α} incident with the first edge of P̃ (the edge incident with a). In all these cases we have P ⊆ G, because P̃ has no vertex in A^{∗} other than possibly a. And no vertex of P other than possibly its last vertex lies in B, because B ∩ V = B̃ ∩ Ṽ and any new initial segment of P lies in a subgraph G_{λ} − S_{λ} of G which avoids B by Lemma 3.2 (i).

It remains to check that the paths P just defined have distinct last points in B even when the last points of the corresponding paths P̃ are ends. However if P̃ ends in β′ ∈ B̃ then its tail P̃ − a ⊆ P ⊆ G is equivalent in G̃ to some ray in β′ ∩ β, by definition of β′. By (8) this implies P̃ − a ∈ β, so the last point of P is β ∈ B. And since the map β ↦ β′ is well defined, these last points differ for distinct P, because the corresponding paths P̃ have different endpoints β′ by assumption.

We still need an A–B separator on P. The only vertices x ∈ X̃ that do not lie on the path P obtained from the path P̃ containing x are points in A^{∗}. So let X be obtained from X̃ by replacing every end β′ ∈ X̃ ∩ B̃ with the corresponding end β ∈ B and replacing every a_{α} ∈ X̃ ∩ A^{∗} with the end α ∈ A. Since P ∈ P starts in α if P̃ starts in a_{α} (and P ends in β if P̃ ends in β′), this set X consists of a choice of one point from every path in P.

Let us then show that

X is an A–B separator in G.  (9)

Suppose there exists a path Q ⊆ G − X that starts in A and ends in B. Lemma 3.2 (v) enables us to choose Q as a path starting in A \ I. Our aim is to turn Q into an Ã–B̃ path Q′ in G̃ that avoids X̃, which contradicts the choice of X̃.

If Q meets ⋃ D_{1}, it has a last vertex there by (7), in D ∈ D_{1}(λ), say. Its next vertex a lies in U_{λ}, by the definition of D. We then define (for the time being) Q′ as the final segment aQ of Q starting at a. If Q has no vertex in ⋃ D_{1}, then either the first point of Q is a vertex a ∈ A ∩ Ã (in which case we put Q′ := Q), or Q starts at an end α ∈ A\I. By Lemma 3.2 (iv), there exists a λ < μ^{∗} such that α ∈ \overline{G}_{λ}, which implies α ∈ O_{λ}. We make a := a_{α} the starting vertex of Q′ and continue Q′ along Q, beginning with the last D_{α}–G̃ edge on Q. Our assumption of α ∉ X implies that a_{α} ∉ X̃, by the definition of X. Thus in the first two cases, Q′ is now a path in G − ⋃ D_{1}; in the third, Q′ is a path in (G − ⋃ D_{1})/D_{α}, which starts at the vertex a ∈ Ã and avoids X̃.

However, Q′ may still meet D_{2}. And although we know from (7) that Q′ has a last vertex in ⋃ D_{2}, say in D_{α′}, we cannot simply shorten Q′ to a path a_{α′}Q′ in G̃, because it may happen that a_{α′} ∈ X̃. Instead, we will use Lemma 3.4 to replace any segments of Q′ that meet some D_{α} ∈ D_{2} (with a_{α} ≠ a) by paths through the corresponding G_{μ} that avoid X̃. As we only have to deal with a finite initial segment of Q′ and the D_{α} are all disjoint, we are able to modify Q′ step by step. Eventually, we will obtain a (walk that can be pruned to a) path Q′ in G̃ that avoids X̃, yielding the desired contradiction.

So consider a segment of Q′ that meets some D_{α} ∈ D_{2}. By definition of D_{α} we may assume that segment to be a T_{μ}-path sQ′t in H_{μ}, where μ is such that D_{α} ⊆ G_{μ}. By definition of H′_{μ} (which is a subgraph of G̃ by Lemma 3.2 (iii), i.e. no parts of H′_{μ} were deleted or contracted when we defined G̃), there are |S_{μ}| + 1 paths from s to t in H′_{μ} that are disjoint outside sQ′t. But H′_{μ} contains at most |S_{μ}| vertices from X̃: since these lie on disjoint paths ending in B̃ and S_{μ} separates H′_{μ} ⊆ G_{μ} from B in G and hence from B̃ in G̃, all of these paths must meet S_{μ}. So one of our |S_{μ}| + 1 s–t paths in H′_{μ} avoids X̃, and we can use this path to replace sQ′t on Q′. This completes the proof of (9).

We can now repeat the reduction for the ends of B.

Lemma 3.6. Let G = (V, E, Ω) be a graph, and let A, B ⊆ V ∪ Ω be such that A ∩ \overline{B} = ∅ = \overline{A} ∩ B. Then there are a minor G′ of G and sets A′, B′ ⊆ V (G′) satisfying

(i) |A′| ≤ |A|,

(ii) G satisfies the Erdős-Menger conjecture for A and B if G′ satisfies it for A′ and B′.

Proof. Apply Lemma 3.5 twice, once for A and once for B.

By Lemma 3.6, we already have the main case of Theorem 2.2:

Proposition 3.7. Let G = (V, E, Ω) be a graph, let A, B ⊆ V ∪ Ω be such that (\overline{A} \ A) ∩ B = ∅ = A ∩ (\overline{B} \ B), and let A be countable. Then G satisfies the Erdős-Menger conjecture for A and B.

Proof. Use Lemmas 3.1 and 3.6, and Theorem 1.1.

The next section will be spent on strengthening Proposition 3.7 to the full generality of Theorem 2.2.

4 Countable separators

In this section we prove Theorem 2.2. But first, let us establish a weaker version in which the separator X also satisfies A ∩ (\overline{X} \ X) = ∅:

Lemma 4.1. Let G = (V, E, Ω) be a graph, let A, B ⊆ V ∪ Ω satisfy A ∩ \overline{B} = ∅ = \overline{A} ∩ B, and suppose there exists a countable A–B separator X ⊆ V ∪ Ω in G with A ∩ (\overline{X} \ X) = ∅. Then G satisfies the Erdős-Menger conjecture for A and B.

Proof. First, we find a countable A–B separator Y and a set P_{Y} of disjoint Y –A paths satisfying

(a) in every y ∈ Y there starts a path of P_{Y};

(b) Y ∩ Ω ⊆ A ∪ B;

(c) (\overline{Y} \ Y) ∩ B = ∅ = Y ∩ (\overline{B} \ B).

We may clearly assume that X ∩ Ω ⊆ A ∪ B. As \overline{A} ∩ B = ∅, this implies that X ∩ (\overline{A} \ A) = ∅. As also A ∩ (\overline{X} \ X) = ∅ and X is countable, we can use Proposition 3.7 to obtain a set P_{1} of disjoint X–A paths and an X–A separator Y on P_{1} in G.

We claim that Y together with the set

P_{Y} := {yP | P ∈ P_{1} and y ∈ Y ∩ P }

of disjoint Y –A paths is as desired.

Indeed, Y is countable because P_{1} is. Further, Y is an A–B separator in G: any path starting in B and ending in A meets X and thus has a subpath P starting in X and ending in A. But then P also meets Y. The conditions (a) and (b) are easily checked; for the latter recall that we assumed X ∩ Ω ⊆ A ∪ B.

Next, we show (c). By (b), any end α ∈ Y ∩ (\overline{B} \ B) lies in A ∩ \overline{B}, which is empty by assumption. Now consider an end β ∈ (\overline{Y} \ Y) ∩ B. Every neighbourhood of β contains a point of Y; it even contains infinitely many points of Y, as otherwise we could find a neighbourhood containing no point of Y. Choose a neighbourhood Ĉ(S, β) of β that contains no point of A (which is possible, as \overline{A} ∩ B = ∅). The infinitely many points of Y lying in Ĉ(S, β) are linked to A by disjoint paths in P_{Y}. All of these infinitely many paths must meet the finite set S, a contradiction. Therefore, (c) is proved.

Having found Y and P_{Y}, we now apply Proposition 3.7 again, this time for the sets Y and B. Thus, we get a system P_{2} of disjoint B–Y paths and a B–Y separator Z on P_{2} in G.

Finally, let P be the system of disjoint B–A paths obtained by concatenating every B–Y path P ∈ P_{2} with the unique Y –A path P′ ∈ P_{Y} from (a) that starts at the endpoint of P. Note that these are indeed paths: if P terminates in an end ω ∈ Y then, by (b), ω ∈ A or ω ∈ B. In the former case P′ is trivial, in the latter case P. Clearly, Z lies on P. All that is left to show is that Z is also an A–B separator. So consider a path P that starts in A and ends in B. By definition of Y, P meets Y and thus has a subpath starting in Y and ending in B. This subpath cannot avoid the Y –B separator Z.

We can now complete the proof of Theorem 2.2, which we restate:

Theorem 2.2. Let G = (V, E, Ω) be a graph, let A, B ⊆ V ∪ Ω satisfy A ∩ \overline{B} = ∅ = \overline{A} ∩ B, and suppose that there exists a countable A–B separator X ⊆ V ∪ Ω in G. Then G satisfies the Erdős-Menger conjecture for A and B.

Proof. We will start by constructing a set A′ ⊆ A and a countable A′–B separator X′ with

(\overline{X′} \ X′) ∩ A′ = ∅,  (10)

to which we will then apply Lemma 4.1.

Using Lemma 3.2 with

A_{Ω} := (\overline{X} \ X) ∩ A,

we find I, μ^{∗} and families (G_{μ})_{μ<μ^{∗}} and (S_{μ})_{μ<μ^{∗}} satisfying the assertions (i)– (v) of Lemma 3.2. As before, write C_{μ} := G_{μ} − S_{μ}. Setting A′ := A \ I and

X′ := ⋃_{μ<μ^{∗}} S_{μ} ∪ (X \ ⋃_{μ<μ^{∗}} \overline{C_{μ}})

we claim that X′ is a countable A′–B separator satisfying (10).

To see that X′ is countable, recall that the sets \overline{C_{μ}} are disjoint for different μ (Lemma 3.2 (iii)), and that each \overline{C_{μ}} with S_{μ} ≠ ∅ contains an end α ∈ A_{Ω} (Lemma 3.2 (ii)). Since α ∈ \overline{X} (by definition of A_{Ω}), we have \overline{C_{μ}} ∩ X ≠ ∅, so by the countability of X there are only countably many such μ.

Let us now show that X′ is an A′–B separator. Consider a path Q from A′ to B. Since X is an A–B separator, Q must meet X. If Q meets X outside X′, it meets X in \overline{C_{μ}} for some μ < μ^{∗}. By Lemma 3.2 (i), however, Q cannot be contained in \overline{C_{μ}}, so Q meets S_{μ} ⊆ X′.

To prove (10), suppose there is an end ω ∈ (\overline{X′} \ X′) ∩ A′. Let us show first that

ω ∉ \overline{X}.  (11)

Suppose otherwise; then we have either ω ∈ (\overline{X} \ X) ∩ A = A_{Ω} or ω ∈ X \ X′. In both cases (in the first by Lemma 3.2 (iv), observe that ω ∉ I as ω ∈ A′; in the second by construction of X′) there is a μ < μ^{∗} with ω ∈ \overline{G_{μ}}. Then by Lemma 3.2 (iii), the sets of the form Ĉ(S_{μ}, ω) are neighbourhoods of ω that avoid X′, contradicting ω ∈ \overline{X′} \ X′.

By (11), there exists a finite set S such that C(S, ω) ∩ X = ∅. By our choice of ω, however, C(S, ω) contains infinitely many vertices from X′, and hence from X′ \ X ⊆ ⋃_{μ<μ^{∗}} S_{μ}. Since each S_{μ} is finite, we can thus find infinitely many μ < μ^{∗} and corresponding vertices s_{μ} ∈ S_{μ} ∩ C(S, ω) that are distinct for different μ. By Lemma 3.2 (ii) and S_{μ} = N(C_{μ}), each s_{μ} sends a path P_{μ} ⊆ \overline{G[C_{μ} ∪ \{s_{μ}\}]} to an end in A_{Ω} ⊆ \overline{X}. These P_{μ} are disjoint by Lemma 3.2 (iii), so only finitely many of them meet S. Every other P_{μ} lies entirely in \overline{C}(S, ω), so \overline{C}(S, ω) ∩ \overline{X} ≠ ∅. But then also C(S, ω) ∩ X ≠ ∅, contradicting our choice of S. This establishes (10).

Applying Lemma 4.1 to A′,B and the separator X′ (note that \overline{A′} ∩ B = ∅ = A′ ∩ \overline{B}, as A′ ⊆ A), we obtain a set P of disjoint A′–B paths and an A′–B separator on P, which by Lemma 3.2 (v) is also an A–B separator.

5 Disjoint closures

We restate our second main result, which we shall prove in this section.

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

Our proof follows that of Theorem 1.2 as given in [7], and in addition we will draw on techniques from the proof of Lemma 3.5. Our aim is to reduce our problem to rayless graphs, and then apply Theorem 2.4. We thus need to dispose of the ends in G, which will be achieved in three steps. First, we delete all ends in \overline{A}. More precisely, we reduce the problem to a minor G′ of G and to sets A′, B′ so that the closure of A′ contains no ends. In the next step we repeat this procedure for B′. To preserve what we have gained in the first step, we have to be careful that no new ends are introduced into \overline{A′}. All this amounts to the following lemma:

Lemma 5.1. Let G = (V, E, Ω) be a graph, and let A, B ⊆ V ∪ Ω be such that \overline{A} ∩ \overline{B} = ∅. Then there exists a minor G′ = (V′, E′, Ω′) of G and sets A′, B′ ⊆ V′ ∪ Ω′ that satisfy the following conditions:

(a) Ω′ ∩ \overline{A′} = ∅ (in particular A′ ⊆ V′);

(b) if Ω ∩ \overline{B} = ∅ then Ω′ ∩ \overline{B′} = ∅ (and in particular B′ ⊆ V′); (c) \overline{A′} ∩ \overline{B′} = ∅; and

(d) the Erdős-Menger conjecture holds for A and B in G if it holds for A′ and B′ in G′.

Two applications of Lemma 5.1, one for A and another for B, reduces our problem to the case that G has no ends in \overline{A} ∪ \overline{B}. We then eliminate the remaining ends by the following lemma from [7]:

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

Finally, we apply Theorem 2.4 to complete the proof.

It thus remains to establish Lemma 5.1. We shall need the following easy lemma from [9]:

Lemma 5.3. [9] Let G be a connected graph, and let U ⊆ V (G) 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.

Proof of Lemma 5.1. First, we construct a subgraph M ⊆ G whose closure does not contain ends of \overline{A}. More formally, our aim is that in |G|

Ω ∩ \overline{A} ∩ \overline{M} = ∅.  (12)

Our desired graph G′ will then be obtained from a supergraph of M.

We define M by transfinite ordinal recursion, as a limit M = ⋂_{μ≤μ^{∗}} M_{μ} of a well-ordered descending family of subgraphs M_{μ} indexed by ordinals. Put M_{0} := G, and for a limit ordinal μ ≠ 0 let M_{μ} := ⋂_{μ′<μ} M_{μ′}. Now, consider a successor ordinal μ + 1. If Ω ∩ \overline{A} ∩ \overline{M_{μ}} = ∅ put μ^{∗} := μ and M := M_{μ}, and terminate the recursion. Otherwise, there is an α_{μ} ∈ Ω∩\overline{A}∩\overline{M_{μ}}. Since \overline{A}∩\overline{B} = ∅, we can choose a finite vertex set L_{μ} such that the open neighbourhood Ĉ(L_{μ}, α_{μ}) is disjoint from B. Put C_{μ} := C(L_{μ}, α_{μ}) and M_{μ+1} := M_{μ} − C_{μ}. Observe that C_{μ} ∩ M_{μ} is never empty as α_{μ} ∈ \overline{M_{μ}}. Thus, the recursion terminates.

Let C be the set of components of G−M. For every C ∈ C put S_{C} := N_{G}(C), G_{C} := G[V (C)∪S_{C}] and A_{C} := A∩\overline{G_{C}}. We shall now proceed in a similar way as in the proof of Lemma 3.5: in order to obtain G′ we will delete and contract certain connected subgraphs, each of which will lie in a C ∈ C. Thus, the G_{C} here play a similar role as the G_{μ} in Lemma 3.5. Now, in contrast to the set of neighbours S_{μ} we deal with there, the sets S_{C} here are not necessarily finite. Consequently, it may happen that two C ∈ C do not have disjoint closures. However, for our purposes it is sufficient to know that no end in A lies in the closure of two elements of C:

A_{C} ∩ A_{D} ⊆ S_{C} ∩ S_{D} for two different C, D ∈ C  (13)

Indeed, suppose there is an end α ∈ A_{C} ∩A_{D} = A∩\overline{G_{C}} ∩\overline{G}_{D}. Then every neighbourhood Ĉ(T, α) of α contains vertices of both G_{C} and G_{D}. Being connected, C(T, α) also contains a G_{C}–G_{D} path, and therefore a vertex of S_{C} ⊆ V (M). This implies α ∈ \overline{M}, a contradiction to (12). As no vertices other than those of S_{C} ∩ S_{D} lie in A_{C} ∩ A_{D}, (13) is proved.

Now, consider a given C ∈ C. Although S_{C} may be infinite it can be separated from A_{C} by finitely many vertices and ends. Indeed, we claim that

\overline{G_{C}} contains a finite set P_{C} of disjoint S_{C}–A_{C} paths and a S_{C}–A_{C}
separator X_{C} on P_{C}.

(14)

First, consider a non-trivial S_{C}–A_{C} path P. P is either completely contained in G_{C} or in G − C. Suppose the latter. Then P terminates in an end α ∈ A_{C}. By (13), P can meet every D ∈ C only finitely often, hence it meets M infinitely often, a contradiction to (12). Thus, every S_{C}–A_{C} path lies completely in G_{C}.

Next, let us show that each set of disjoint S_{C}–A_{C} paths in G_{C} is finite. So suppose there is a an infinite set P_{1}, P_{2}, … of such paths. Let S ⊆ S_{C} be the set of first vertices of the P_{i}. We claim there is a comb in G with teeth in S. If not, applying Lemma 5.3 to H := C ∪ ⋃_{i∈ℕ} P_{i} we obtain a subdivided infinite star with leaves in S. Since each vertex s ∈ S has degree 1 in H, the centre v of the star must lie in C. Let μ be the step when v was deleted from G, i.e. μ := min{μ′ | v ∈ V (C_{μ′})}. Then, the finite set L_{μ} separates v from S, which is impossible. Thus, there is a comb with teeth in S. Let ω ∈ Ω be the end of its spine. Then every neighbourhood of ω contains infinitely many vertices of S and then also infinitely many of the P_{i}. Consequently, infinitely many elements of A lie in the neighbourhood. Thus, ω ∈ \overline{S_{C}} ∩ \overline{A} ⊆ \overline{M} ∩ \overline{A}, a contradiction to (12).

Taking an inclusion-maximal (and hence finite) set of disjoint S_{C}–A_{C} paths in G we see that S_{C} is separated from A_{C} in G by a countable separator (namely by the union of the vertex sets of the paths together with the set of last points). Furthermore, (12) implies \overline{S_{C}} ∩ A_{C} ∩ Ω = ∅. Thus, by Lemma 3.1 and Theorem 2.2, there is a set P_{C} of disjoint S_{C}–A_{C} paths in G and a separator X_{C} on P_{C}. By the preceding arguments, P_{C} is a finite set of paths in G_{C}, which establishes (14).

For C ∈ C, put U_{C} := X_{C} ∩ V and O_{C} := X_{C} ∩ Ω. As in the proof of Lemma 3.5 we will delete certain subgraphs of G_{C} that lie “behind” U_{C} and contract others that contain ends of O_{C}. First of all, we see that U_{C} separates S_{C} from A_{C} \ O_{C}. This is exactly the same as (3) in the proof of Lemma 3.5.

We then define D_{1}(C) as the set of all the components D of G − U_{C} whose closure \overline{D} meets A_{C} \ O_{C}. Because U_{C} is an S_{C}–(A_{C} \ O_{C}) separator, these components satisfy D ⊆ G_{C} − S_{C}, and their neighbourhood N(D) ⊆ U_{C} in G is finite. Also, \overline{D} ∩ O_{C} = ∅ for all D ∈ D_{1}(C), which can be proved as (4) of Lemma 3.5. We put H_{C} := G_{C} − ⋃ D_{1}(C) and see that G_{C} contains a set of disjoint H_{C}–A_{C} paths whose set of first points is U_{C}.

To find the subgraphs which will be contracted, we extend in the proof of Lemma 3.5 the finite set U_{μ} ∪ S_{μ} to a finite set T_{μ} that separates the ends in O_{μ} pairwise. This enables us to apply Lemma 3.4. Here, S_{C} may be an infinite set, so to find a suitable finite set T_{C} we cannot use a superset of S_{C}. Instead, consider for each α ∈ O_{C} the ordinal μ_{α} for which α ∈ \overline{C_{μ_{α}}}. Then, the finite set L_{μ_{α}} separates α from S_{C} ⊆ V (M). The union of these finitely many finite sets together with U_{C} can be taken as the finite set T_{C} we need for Lemma 3.4.

Define H′_{C} as the finite subgraph of H_{C} containing T_{C} which Lemma 3.4 provides for k := |T_{C}| + 1, and for each α ∈ O_{C} let D_{α} be the component of G − H′_{C} to which α belongs. Finally, we set D_{2}(C) := {D_{α} | α ∈ O_{C}} and D_{i} := ⋃_{C∈C} D_{i}(C), i = 1, 2. By deleting all subgraphs in D_{1} and by contracting each subgraph D_{α} ∈ D_{2} to a vertex a_{α} we obtain the graph G̃ = (Ṽ , Ẽ, Ω̃). We put

Ã := (A \ ⋃_{C∈C} A_{C}) ∪ ⋃_{C∈C} U_{C} ∪ {a_{α} | D_{α} ∈ D_{2}}.

Observe that Ã ⊆ Ṽ because of (12).

Let us show that (a) holds for Ã in G̃. Indeed, suppose not. Then, there is by Lemma 2.1 a comb K̃ ⊆ G̃ with teeth in Ã and spine R, say. Consider a R–Ã path P of the comb. If P ends in a vertex of U_{C} for some C ∈ C then we extend P using the corresponding path in P_{C} to a R–A path. If P ends in one of the contracted vertices a_{α} we substitute its last edge by a path through D_{α} ending in α so that again we obtain a R–A path. Because of (13), and since the D_{α} and all the paths in ⋃_{C∈C} P_{C} are disjoint, all these changed paths are still disjoint. Thus we have found a comb K ⊆ G with spine R and teeth in A. Only finitely many of the R–A paths of K may meet M as otherwise the end of R lies in the closure of both A and M, a contradiction to (12). Thus, we may assume that K is contained in a C ∈ C. In particular, R ⊆ C ∩ G̃. But the finite set X_{C} separates C ∩ G̃ from A_{C}, contradicting that K contains infinitely many disjoint R–A_{C} paths. This proves (a) for Ã.

Making use of (13), we see in a similar way as in the proof of Lemma 3.5, that every ray R of an end β ∈ B has a tail in G ∩ G̃. There thus is a β′ ∈ Ω̃ with β ∩ β′ ≠ ∅ and it can be shown as in the proof of Lemma 3.5 that this mapping is injective. Put

B̃ := (B ∩ V) ∪ {β′ | β ∈ B ∩ Ω} ⊆ Ṽ ∪ Ω̃.

The graph G̃ together with the sets Ã and B̃ is almost what we want. Indeed, (a) is satisfied and below we shall see that (b) and (d) hold as well. Only (c) fails since Ã and B̃ may share some vertices. However, \overline{Ã} does not contain ends by (a). Thus

∅ = \overline{Ã} ∩ \overline{B̃} ∩ Ω̃ = (\overline{Ã} \ Ã) ∩ (\overline{B̃} \ B̃).

Now, in a similar way as in Lemma 3.1 we find sets A′ and B′ in the graph G′ := G̃ − (Ã ∩ B̃) such that (c) holds and properties (a), (b) and (d) are preserved. Therefore, to finish the proof it suffices to show (b) and (d) for Ã and B̃ in G̃.

For (b), assume that Ω̃ ∩ \overline{B̃} ≠ ∅. Then either B̃ contains ends, or there is an end ω ∈ Ω̃ such that every neighbourhood Ĉ(S, ω) in G̃ contains vertices of B̃. In the latter case, by (a), we may suppose that Ĉ(S, ω) does not contain vertices of Ã, and thus view it as a neighbourhood in G containing vertices of B. Thus, in both cases, Ω ∩ \overline{B} ≠ ∅, which proves (b).

The proof of (d) is completely analogous to the proof of (iv) in Lemma 3.5. Note that when we change the set P̃ of disjoint Ã–B̃ paths into A–B paths, the paths still have, by (13), distinct first points.

References

[1] R. Aharoni. Menger’s theorem for graphs containing no infinite paths. Europ. J. Combinatorics, 4:201–204, 1983.

[2] R. Aharoni. Menger’s theorem for countable graphs. J. Combin. Theory (Series B), 43:303–313, 1987.

[3] R. Aharoni. A few remarks on a conjecture of Erdős on the infinite version of Menger’s theorem, in (R.L. Graham & J. Nesetril, eds.): The Mathematics of Paul Erdős II, Springer-Verlag, Heidelberg 1997.

[4] R. Aharoni and R. Diestel. Menger’s theorem for a countable source set. Comb., Probab. Comput., 3:145–156, 1994.

[5] R. Diestel. Graph Theory (2nd edition). Springer-Verlag, 2000. Electronic edition available at:

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

[6] R. Diestel. The countable Erdős-Menger conjecture with ends. J. Combin. Theory (Series B), 87:145–161, 2003.

[7] R. Diestel. The Erdős-Menger conjecture for source/sink sets with disjoint closures. To appear in J. Combin. Theory (Series B).

[8] R. Diestel. The cycle space of an infinite graph. To appear in Comb., Probab., Computing.

[9] R. Diestel and D. Kühn. Graph-theoretical versus topological ends of graphs. J. Combin. Theory (Series B), 87:197–206, 2003.

[10] H.A. Jung. Connectivity in infinite graphs. In L. Mirsky, editor, Studies in Pure Mathematics. Academic Press, 1971.

[11] C.St.J.A. Nash-Williams, Infinite graphs, a survey, J. Combin. Theory (Series B), 3:286–301, 1967.

[12] N. Polat, Sur une extension du théorème de Menger aux graphes infinis, European J. Combin., 4:359–365, 1983.

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

Version 8 September 2004

Henning Bruhn <hbruhn@nullsinn.net>
Reinhard Diestel <diestel@math.uni-hamburg.de>
Maya Stein <fm7y052@public.uni-hamburg.de>

Mathematisches Seminar Universität Hamburg Bundesstraße 55 20146 Hamburg Germany