Menger’s theorem for infinite graphs 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 by reducing it to the vertex version, which was recently proved by Aharoni and Berger.

1 Introduction

Erdős conjectured (see [6]) 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.

A proof of this conjecture has recently been obtained by Aharoni and Berger [1].

There is a natural extension of the Erdős-Menger conjecture in which the sets A and B may contain ends as well as vertices. Here, 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.

In this paper we prove the extended ends version of the conjecture by reducing it to the vertex version. Our proof uses a refinement of techniques developed in [3], where this reduction was carried out for countable graphs.

The Erdős-Menger conjecture for ends is not true for arbitrary sets A and B (of vertices and ends): a necessary condition is that the closure of A in the topological space |G| associated with the graph G and its ends does not meet B, and vice versa. A comprehensive introduction to this space is given in [2], and we recall the basic definitions in Section 2. In those terms, our main result can be stated as follows:

Theorem 1.1. Let G = (V, E, Ω) be a graph and let A, B ⊆ V ∪ Ω be such that A ∩ \overline{B} = ∅ = \overline{A} ∩ B, the closures being taken in |G|. Then G satisfies the Erdős-Menger conjecture for A and B.

One may also consider a purely topological version of the Erdős-Menger conjecture, in which P is any set of A–B arcs in the space |G|, and the set X is required to meet every A–B arc in |G|. This version of the conjecture can fail unless A and B have disjoint closures in |G|. But in that case it can be reduced to Theorem 1.1 (see [3]), so the purely topological version offers nothing new.

2 Definitions and statement of result

The basic terminology we use can be found in [2]. 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 [2, 4, 5] 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.

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.

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.

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 terms needed to state our main result are now precisely defined. We shall prove the following slight strengthening of Theorem 1.1 which, as in the vertex case, allows the intersection of A and B itself to be non-empty:

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

We remark that the disjointness condition in Theorem 2.2 is necessary [3]; a counterexample for when it is violated is given in [3]. The condition means that any ray whose end lies in A can be separated from B by a finite set of vertices, and vice versa with A and B interchanged. Note that this does not imply the much stronger condition that A and B can be finitely separated, in which case the proof is immediate by standard alternating path techniques [3]. A more typical example for the disjointness condition is to take as A and B distinct levels of vertices in a tree: if the tree is ℵ_{0}-regular, for example, it contains infinitely many disjoint paths between these levels, so A and B have disjoint closures (in fact, are closed and disjoint) but cannot be finitely separated.

3 Proof of the theorem

Our aim is to reduce the ends version of the Erdős-Menger conjecture, Theorem 2.2, to the original vertex version as stated in the Introduction and recently proved by Aharoni and Berger.

We begin by showing that, as in the vertex case of the conjecture, we may assume without loss of generality that A∩B = ∅. In the vertex case, one simply deletes A∩B from the graph, finds a path system and separator in G−(A∩B), and then adds the deleted vertices both to the path system (as singleton A–B paths) and to the separator, to obtain a solution for G. When A ∩ B is infinite, however, deleting it can result in the destruction or splitting of ends. Before we allow ourselves to assume that A ∩ B = ∅, therefore, we have to make sure that this will not affect any ends in A or B. Our first lemma ensures this, and thereby reduces the stronger form of our theorem (Theorem 2.2) to the version stated in the introduction, Theorem 1.1.

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 the following conditions:

(i) if A ⊆ V then A′ ⊆ A, and if B ⊆ V then B′ ⊆ B;

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

(iii) 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, these satisfy (i). Moreover, A′ ∩B′ is still empty, so the disjointness assumption stated in the lemma implies (ii).

For (iii), 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 with the A–B separator X := X′ ∪ (A ∩ B) on it.

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. [3] 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. [7, 3] 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 1.1 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 exist a minor G′ = (V′, E′, Ω′) of G and sets A′ ⊆ V′ and B′ ⊆ V′ ∪ Ω′ satisfying the following conditions:

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

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

(iii) 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)–(iii), 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 (ii). Assertion (i) follows from the definition of B̃ and Lemma 3.1 (i).

We now prove assertion (iii) 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).

Proof of Theorem 2.2: Let G = (V, E, Ω) be given, and let A, B ⊆ V ∪ Ω be such that A ∩ (\overline{B} \ B) = ∅ = (\overline{A} \ A) ∩ B. By Lemma 3.1, we may assume that A ∩ \overline{B} = ∅ = \overline{A} ∩ B. Applying Lemma 3.5 twice, first for A and then for B, we may further assume that A∪B ⊆ V. Now the statement to be proved is Erdős’s conjecture as stated in the Introduction, which has been proved by Aharoni and Berger [1]. □

References

[1] R. Aharoni and E. Berger. Menger’s theorem for infinite graphs. Preprint 2005.

[2] R. Diestel. Graph Theory (3rd edition). Springer-Verlag 2005 (to appear).

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

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

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

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

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

Version 24 January, 2005

Henning Bruhn <hbruhn@gmx.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