Menger’s theorem for a countable source set

Ron Aharoni and Reinhard Diestel

Dedicated to Paul Erdős on the occasion of his 80th birthday

Paul Erdős has conjectured that Menger’s theorem extends to infinite graphs in the following way: whenever A, B are two sets of vertices in an infinite graph, there exist a set of disjoint A–B paths and an A– B separator in this graph so that the separator consists of a choice of precisely one vertex from each of the paths. We prove this conjecture for graphs that contain a set of disjoint paths to B from all but countably many vertices of A. In particular, the conjecture is true when A is countable.

Introduction

If there is any conjecture in infinite graph theory whose fame has clearly transcended the boundaries of the field, it is the following infinite version of Menger’s theorem, conjectured by Erdős:

Conjecture. (Erdős) Whenever A, B are two sets of vertices in a graph G, there exist a set of disjoint A–B paths and an A–B separator in G so that the separator consists of a choice of precisely one vertex from each of the paths.

Here, G may be either directed or undirected and either finite or infinite, and ‘disjoint’ means ‘vertex disjoint’. If G is finite, the statement is clearly a reformulation of Menger’s theorem. A set of A–B paths together with an A–B separator as above will be called an orthogonal paths/separator pair.

We remark that the naïve infinite analogue to Menger’s theorem which merely compares cardinalities, is considerably weaker and easy to prove. Indeed, consider any inclusion-maximal set P of disjoint A–B paths. If P can be chosen infinite then ⋃ P, which is trivially an A-B separator, still has size only |P|. If not, then choose P of maximal (finite) cardinality, and there is a simple reduction to the finite Menger theorem [ 5 ]. This was in fact first observed by Erdős, and seems to have inspired his above conjecture as the ‘true’ generalization of Menger’s theorem.

Although Erdős’s conjecture has been proved for countable graphs [ 2 ], a full proof still appears to be out of reach. However, no other conjecture in infinite graph theory has inspired as interesting a variety of partial or related results as this one; see [ 4 ] for a survey and list of references.

The main aim of this paper is to prove a lemma which, in addition to implying (with [ 2 ]) the results stated in the abstract, might play a role in an overall proof of the conjecture by induction on the size of G. Briefly, the lemma implies that if the conjecture is true for all graphs of size κ, where κ is any infinite cardinal, then it is true also for arbitrary graphs provided the source set A is no larger than κ. (In particular, we see that the conjecture holds for any graph if A is countable.) Now if |A| = |G| = λ and the conjecture holds for all graphs of size < λ, the lemma enables us to apply the induction hypothesis to G with A replaced by its smaller subsets A′; we may then try to combine the orthogonal paths/separator pairs obtained between these A′ and B to one between A and B. We must point out, however, that such a proof of Erdős’s conjecture will by no means be straightforward, and it is not the only possible approach.

1. Definitions and statement of the main result

All the graphs we consider will be directed; undirected versions of our results can be recovered in the usual way by replacing each undirected edge with two directed edges pointing in opposite directions. An edge from a vertex x to a vertex y will be denoted by xy. When G is a graph, then \overleftarrow{G} denotes the graph obtained from G by reversing all its edges.

Paths, likewise, will be directed, and we usually refer to them by their vertex sequence. If P = x … y is a path and v, w are vertices on P in this order, then vP w denotes the subpath of P from v to w. Similarly, we write P v and vP for initial and final segments of P, P v̊ for P v − v, v̊P for vP − v, and so on. If Q = y … z is another path, and P ∩ Q = { y }, then P yQ denotes the path obtained by concatenating P and Q.

Let X, Y be sets of vertices in a graph. An X–Y path is a path from X to Y whose inner vertices are neither in X nor in Y. If x is a vertex, then a set of { x }–Y paths that are disjoint except in x is an x–Y fan; the fan is onto if every vertex in Y is hit. Similarly, a set of X–y paths that are disjoint except in y is an X–y fan.

A warp is a set of disjoint paths. When W is a warp, we write V [W] for the set of vertices of the paths in W, and E[W] for the set of their edges. Similarly, we write in [W] for the set of initial vertices of the paths in W, and ter [W] for the set of their terminal vertices. For a vertex x ^{∈} V [W], we denote the path in W containing x by Q_{W}(x), or briefly Q(x). For x /^{∈} V [W], we put Q_{W}(x) := \{ x \}. A warp consisting of A–B paths is an A–B warp. By \overleftarrow{W} we denote the warp in \overleftarrow{G} consisting of the reversed paths from W.*

* Clearly, \overleftarrow{\overleftarrow{W}} = W. We shall use this fact as an excuse to denote warps in \overleftarrow{G}, if they are introduced afresh rather than being obtained from a warp in G, by \overleftarrow{W} etc. straight away;

Let G = (V, E) be a graph and A, B ⊆ V. Any such triple Γ = (G, A, B) will be called a web. The web (\overleftarrow{G}, B, A) is denoted by \overleftarrow{Γ}. An A–B warp W with in [W] = A is a linkage in Γ, and Γ is linkable if it contains a linkage.

A set S ⊆ V separates A from B in G if every path in G from A to B meets S. Note that A and B may intersect, in which case clearly A ∩ B ⊆ S.

A warp W in G is called a wave in Γ if V [W] ∩ A = in [W] and ter [W] separates A from B in G. The wave {(a) | a ^{∈} A} is called the trivial wave. If W is a wave in Γ then Γ/W denotes the web

( G − (A\in [W]) − (V [W]\ter [W]) , ter [W] , B ) .

In every web Γ = (G, A, B) there is a wave W such that Γ/W has no nontrivial wave. (This is not difficult to see. If W_{0} is a wave in Γ and W_{1} is a wave in Γ/W_{0}, then W_{1} defines a wave in Γ in a natural way: just extend its paths back to A along the paths of W_{0}. This wave in Γ is ‘bigger’ than W_{0}, and chains of waves in Γ with respect to this order tend to an obvious limit wave W, which consists of the paths that are eventually in every wave of the chain. If the chain was maximal, then Γ/W has no non-trivial wave. See [ 2 ] for details.)

A wave W in Γ is a hindrance if A\in [W] ≠ ∅; if Γ contains a hindrance, it is called hindered. Note that every hindrance is a non-trivial wave. The following was observed in [ 2 ]:

Erdős’s conjecture is equivalent to the assertion that every unhindered web is linkable.

We are now in a position to state the main result proved in this paper. (For the reasons explained earlier, and because it is of a technical nature, we call it a lemma, not a theorem.)

Lemma 1. Let Γ = (G, A, B) be a web and J an A–B warp in G (possibly empty). If |A\in [J]| > |B\ter [J]|, then Γ is hindered.

Lemma 1 will be proved in Sections 2 and 3. Our aim will be to turn the given warp J, step by step, into a hindrance. This will require some alternating path techniques; the definitions and lemmas needed are given in Section 2. Section 3 is devoted to the main body of the proof of Lemma 1. In Section 4 we look at the implications of the lemma for Erdős’s conjecture.

their reversals in G will then be denoted by W. The idea here is to avoid the counter-intuitive practice of having a warp W in \overleftarrow{G} and a resulting warp \overleftarrow{W} in G. This convention, if not its explanation, should help the reader to avoid any warps in his or her intuition when such things are discussed briefly in Section 4.

2. Alternating paths

Let Γ = (G, A, B) be a web, and let J be an A–B warp in G. A finite sequence P = x_{0}e_{0}x_{1}e_{1} … e_{n−1}x_{n} of not necessarily distinct vertices x_{i} and distinct (directed) edges e_{i} of G will be called an alternating path (with respect to J) if the following three conditions are satisfied:

(i) for every i < n, either e_{i} = x_{i}x_{i+1} ^{∈} E(G)\E[J] or e_{i} = x_{i+1}x_{i} ^{∈} E[J]; (ii) if x_{i} = x_{j} for i ≠ j then x_{i} ^{∈} V [J]; (iii) for every i, 0 ⩽ i < n, if x_{i} ^{∈} V [J] then { e_{i−1}, e_{i} } ∩ E[J] ≠ ∅.

All the alternating paths we consider in this section will be alternating paths in G with respect to J. Note that, by (iii) above, an alternating path starting at a vertex of J has its first edge in J. As the edges of an alternating path are pairwise distinct, it can visit any given vertex at most twice, and this happens in essentially only two ways: if x_{i} = x_{j} for i < j < n, then x_{i} ^{∈} V [J] by (ii), so by (iii)

either e_{i−1}, e_{j} ^{∈} E[J] and e_{i}, e_{j−1} /^{∈} E[J] (Fig. 1 left)

or e_{i}, e_{j−1} ^{∈} E[J] and e_{i−1}, e_{j} /^{∈} E[J] (Fig. 1 right).

FIGURE 1. Two alternating paths with respect to J

Note that initial segments of alternating paths are again alternating paths, but final segments need not be. Finally, an ordinary path which avoids J or meets it only in its last vertex is trivially an alternating path.

There are analogous alternating versions of the notions of X–Y path, X– y fan and so on.

Lemma 2.1. If a ^{∈} A\in [J] and b ^{∈} B\ter [J], and if P = a … b is an alternating path with respect to J, then G contains an A–B warp J′ such that in [J′] = in [J] ∪ { a } and ter [J′] = ter [J] ∪ { b } and { Q ^{∈} J | P ∩ Q = ∅ } ⊆ J′.

Proof. Consider the graph on V [J] ∪ V (P) whose edge set is the symmetric difference of E[J] and E(P). The (undirected) components of this graph are all finite. Considering their vertex degrees, we see that they are either A–B paths or cycles avoiding A ∪ B (possibly trivial). The assertion follows. □

Lemma 2.2. Let P_{1} = x_{0}e_{0} … e_{n−1}x_{n} and P_{2} = y_{0}f_{0} … f_{m−1}y_{m} be alternating paths. If x_{n} = y_{0}, then there exists an alternating path P_{3} from x_{0} to y_{m} such that V (P_{3}) ⊆ V (P_{1}) ∪ V (P_{2}) and E(P_{3}) ⊆ E(P_{1}) ∪ E(P_{2}).

Proof. Let i ⩽ n be minimal such that there exists a j ⩽ m with the following two properties:

(i) x_{i} = y_{j}; (ii) if x_{i} ^{∈} V [J], then either e_{i−1} ^{∈} E[J] or f_{j} ^{∈} E[J].

(Note that such an i exists, because x_{n} = y_{0} and P_{2} is an alternating path. Moreover, j is easily seen to be unique.) Then x_{0}e_{0} … e_{i−1}x_{i}f_{j} … f_{m−1}y_{m} is an alternating path as desired. □

3. Proof of the main lemma

We now prove Lemma 1. As in the lemma, let Γ = (G, A, B) be a web, and let J be an A–B warp in Γ. Let us write

A_{1} := in [J]  and  A_{2} := A\A_{1}

and

B_{1} := ter [J]  and  B_{2} := B\B_{1},

and put κ:= |B_{2}|. We assume that |A_{2}| > κ, and construct a hindrance W in Γ. Again, all the alternating paths considered in this section will be alternating paths in G with respect to J, unless otherwise stated.

Let us quickly dispose of the case when κ is finite. Assume that κ is minimal such that the lemma fails. By Lemma 2.1 and the minimality of κ, there is no alternating path from A_{2} to B_{2}. For each path Q ^{∈} J, let x(Q) denote the last vertex of Q that lies on some alternating path starting in A_{2}; if no such vertex exists, let x(Q) be the initial vertex of Q. We claim that

W := { Qx | Q ^{∈} J and x = x(Q) }

is a wave in G; since |A_{2}| > κ ⩾ 0 and hence in [W] = in [J] ⫋ A, this wave W will be a hindrance and the lemma will be proved.

To show that W is a wave, we have to prove that ter [W] separates A from B. So let P be any A–B path. Since P is not an alternating path from A_{2} to B_{2}, it meets V [J] and hence V [W]; let y be its last vertex in V [W], and write Q := Q_{J} (y) and x := x(Q). Suppose P avoids ter [W]. Then x ≠ y, and so there exists an alternating path R from A_{2} to y which ends with an edge of W. (Indeed, by definition of W, there is an alternating A_{2}–x path R′; if x′ is the first vertex of R′ on ẙQx, then R′x′ followed by yQx′ in reverse order is an alternating path from A_{2} to y.) By definition of W, R avoids V [J]\V [W] and is thus an alternating path with respect to W. Let z be the first vertex of R on yP. Then either z = y or z /^{∈} V [W], so RzP is again an alternating path with respect to W. By definition of W, RzP avoids V [J]\V [W]. Therefore zP avoids V [J]\{ y } ⊇ B_{1}. (Recall that y /^{∈} B, because y ≠ x and hence y ^{∈} Qx̊.) Thus RzP is an alternating path from A_{2} to B_{2}, a contradiction.

We shall now assume that κ is infinite. To motivate our proof, let us consider the (much easier) case of J = ∅. (This is an important special case, and we recommend that the reader remain aware of it throughout the proof of Lemma 1.) Assume Erdős’s conjecture as true, and let S be an A-B separator as in the conjecture. Then |S| ⩽ |B| = κ. Let us think of the vertices in A as being ‘to the left’ of S, and of those in B as ‘to its right’. Which other vertices of G will be to the left of S? Surely those which cannot be separated from A by ⩽ κ vertices, i.e. which are joined to A by a fan of size > κ. We shall call these vertices ‘popular’. If a popular vertex is in S, it is the starting vertex of a path to B that contains no other popular vertices; let us call such a path ‘lonely’, and its starting vertex ‘special’. The special vertices, i.e. the vertices which are popular and from which we can get to B without hitting any other popular vertex, are in a sense ‘rightmost’ among the popular vertices, even when they are not in S. As we shall see, they turn out to be ‘close enough’ to S that they themselves form the set of endvertices of a hindrance in Γ, which is constructable without reference to S.

For the general case, we follow a similar approach, except that now all the relevant paths and fans will be alternating. Let us call a vertex x ^{∈} V (G)\A_{1} popular if either x ^{∈} A_{2} or there exists an alternating A_{2}–x fan of order > κ. An alternating path P ending in B_{2} and with no inner vertex in A_{2} is called a lonely path if all its vertices are unpopular, except possibly its starting vertex and any vertices x ^{∈} V [J] such that, if e is the edge following x on P, then e /^{∈} E[J]. (In the latter case, the edge preceding x on P must be the edge of J starting in x.) Note that a final segment x_{i}e_{i}x_{i+1} … of a lonely path is again lonely if and only if x_{i} satisfies condition (iii) in the definition of an alternating path, i.e. if and only if e_{i} ^{∈} E[J] when x_{i} ^{∈} V [J].

Our first lemma is merely a technical argument that will be used twice later and has been extracted for economy. The first time we will use it is in the proof of Lemma 3.2 below, and for motivation the reader may prefer to read Lemma 3.2 and its proof first and then return to Lemma 3.1.

Lemma 3.1. Let α be a cardinal, L = { L_{β} | β < α } a family of lonely paths, and M = { M_{β} | β < α } a family of pairwise disjoint alternating paths starting in A_{2}. Assume that, for each β < α, the last vertex of M_{β} is the starting vertex of L_{β}. Then α ⩽ κ.

Proof. Suppose α > κ. For each β < α, let P_{β} be an alternating path from the starting vertex of M_{β} to the final vertex of L_{β} as provided by Lemma 2.2.

Construct an undirected forest H = ⋃_{β<α} H_{β} from these paths, as follows. Let H_{0} be the undirected graph underlying P_{0}. Now let β < α be given, and assume that H_{γ} has been defined for every γ < β. Let z_{β} denote the first vertex of P_{β} that is in B_{2} ∪ V (H_{β}^{−}), where H_{β}^{−} := ⋃_{γ<β} H_{γ}, and let H_{β} be the union of H_{β}^{−} with the undirected graph underlying P_{β}z_{β}. (If z_{β} occurs twice on P_{β}, we take P_{β}z_{β} to stop at the first occurrence of z_{β}.) Since |B_{2}| ⩽ κ and every path P_{β} ends in B_{2}, H has at most κ components. One of these components must have size > κ, so it contains a vertex z of degree > κ. Then z lies on > κ of the paths P_{β}, so z = z_{β} for every β in some set Δ ⊆ α of size > κ.

Let

F := { P_{β}z | β ^{∈} Δ }.

Note that the paths in F are pairwise disjoint except for z, so F is an alternating A_{2}–z fan. Hence, z is popular. As the paths M_{β} are pairwise disjoint, we have z /^{∈} M_{β} for all but at most one β ^{∈} Δ; let us delete this one β from Δ if it exists. Now for all β ^{∈} Δ, we have that z ^{∈} L_{β} and z is not the starting vertex of L_{β} (since this is on M_{β}).

Now consider any β ^{∈} Δ. Since L_{β} is a lonely path and z is popular but not the starting vertex of L_{β}, we have z ^{∈} V [J], and if e denotes the edge following z on L_{β} then e /^{∈} E[J]. (Note that e exists, because z ^{∈} V [J] but L_{β} ends in B_{2}.) Since L_{β} is alternating, this means that the edge f preceding z on L_{β} must be the edge of J starting at z (and such an edge exists). Since z /^{∈} M_{β}, the edge of P_{β} preceding z is precisely this edge f.

As β was chosen arbitrarily, this is true for every β ^{∈} Δ and thus contradicts the fact that for these β the paths P_{β}z̊ are disjoint. □

If the starting vertex of a lonely path is popular, then this vertex is called special; the set of all special vertices outside V [J] is denoted by S. Special vertices will be our prime candidates for the terminal vertices of the hindrance we are seeking to construct. Since the corresponding paths of the hindrance will have to be constructed from the fans connecting A_{2} to these terminal vertices (making them popular), it is important that there are fewer special vertices to be connected in this way than there are connecting paths available from those fans.

Lemma 3.2. There are at most κ special vertices.

Proof. Suppose that { s_{β} | β < κ^{+} } is a set of distinct special vertices, where κ^{+} is the successor cardinal of κ. For each β, let L_{β} be a lonely path starting at s_{β}. Using the popularity of the s_{β}, we may inductively choose a family { M_{β} | β < κ^{+} } of pairwise disjoint alternating paths M_{β} from A_{2} to s_{β}. This contradicts Lemma 3.1. □

Let E denote the set of all those edges in G that lie on some lonely path, and let K be the graph

K := ⋃ J − E.

Let P be the set of all those (undirected) components of K that contain a special vertex or a vertex from A. (Thus, P is a set of pairwise disjoint subpaths of paths in J.) Let

T := { x ^{∈} V (G) | x is the last vertex on some P ^{∈} P } .

We shall define our desired hindrance W in such a way that

ter [W] = S ∪ T.

Lemma 3.3. If P = x … y is a non-trivial component of K and x /^{∈} A, then x is special (and hence P ^{∈} P and y ^{∈} T).

Proof. Let r be the predecessor and s the successor of x on Q(x). Then rx^{∈} E, so there exists a lonely path starting at x with the edge rx. But preceding this path with s does not yield another lonely path (since xs ^{∈} E(P), and hence xs /^{∈} E). Therefore x must be popular (see the definition of lonely paths), and hence special. □

To construct W, let us start from P. Let W_{0} be the set of all paths P ^{∈} P that start in A. (These paths may be entire paths from J, and they may be trivial.) Our aim is to complete W_{0} to our desired wave W by paths of the form a … xP y, where a ^{∈} A_{2} and P = x … y is a path as in Lemma 3.3, together with paths a … s where again a ^{∈} A_{2} and either s ^{∈} S or s is a special vertex in V [J] making up a singleton component of K. It will not be possible to construct W in exactly this way, because the required paths may interfere with the paths in W_{0}. However, such interference will be limited by Lemmas 3.1 and 3.2, and can therefore be overcome by the alternating path tools developed in Section 2.

Let

S′ = { s_{ζ} | ζ < ν ⩽ κ }

be a well-ordering of those special vertices that are either in S or else are the initial vertex of some (possibly trivial) path P ^{∈} P (cf. Lemma 3.2). For each ζ < ν in turn, we shall choose an alternating path P_{ζ} from A_{2} to s_{ζ}, with the following properties:

(i) P_{ζ} ∩ P_{ξ} = ∅ for all ξ < ζ; (ii) P_{ζ} ∩ Q_{J} (s) ⊆ { s_{ζ} } for all s ^{∈} S′; (iii) if Q ^{∈} J and ξ < ζ are such that P_{ξ} ∩ Q ≠ ∅, then P_{ζ} ∩ Q ⊆ { s_{ζ} }; (iv) E(P_{ζ}) ∩ E = ∅.

Let ζ < ν be given, and assume that paths P_{ξ} for all ξ < ζ have been chosen in accordance with (i)–(iv). By (ii), none of these paths contains (s =)s_{ζ}. Since s_{ζ} is popular, there is an alternating A_{2}–s_{ζ} fan F of size > κ. Clearly, at most κ of the paths in F meet any of the paths P_{ξ} (ξ < ζ) or Q(s) for s ^{∈} S′, except, for the latter, in s_{ζ}. Similarly, at most κ of the paths in F meet (in a vertex ≠ s_{ζ}) any path Q ^{∈} J that is hit by some P_{ξ} with ξ < ζ. By Lemma 3.1, at most κ paths of F have an edge in E. (It is straightforward to check that the first edge in E on any path in F starts a lonely path.) We may thus choose P_{ζ} from the paths in F according to (i)–(iv).

Lemma 3.4. For every ζ < ν, we have E(P_{ζ}) ∩ E[J] ⊆ E[W_{0}]. Thus, P_{ζ} is in fact an alternating path with respect to W_{0}.

Proof. If e ^{∈} E(P_{ζ}) ∩ E[J] then, by (iv) above, there is a component P of K containing e. By (ii), the initial vertex of P is not in S′, and is therefore not special. By Lemma 3.3, therefore, the starting vertex of P must be in A, and so P ^{∈} W_{0}. □

Applying Lemma 2.1 ν times with the paths P_{ζ}, we now turn W_{0} into a warp from A onto ter [W_{0}]∪S′ with at most κ initial points in A_{2}. (Here we use that fact that, by (iii) above, no two of the alternating paths P_{ζ} use the same path in W_{0} to alternate on.) By (ii) above, the paths in P that start at the vertices in S′\S extend this warp to a warp W. By Lemma 3.3, ter [W] = S ∪ T as desired.

To prove that W is a wave in Γ, it remains to show that the set S ∪ T separates A from B; note that then W is also a hindrance, since |in [W] ∩ A_{2}| = |S′| ⩽ κ by construction.

In order to prove that S ∪ T separates A from B, consider any A–B path P = a … b in G. Suppose P avoids S ∪ T.

Lemma 3.5. Either b ^{∈} B_{2}, or b is the final vertex of an edge in E ∩ E[J]. In either case, b is not special but starts a lonely path.

Proof. Suppose first that b ^{∈} B_{2}. Then b is not special, because b /^{∈} S. Moreover, { b } is a trivial lonely path.

Suppose now that b ^{∈} B_{1}, and let P′ = x … b be the component of K containing b. As b /^{∈} T, we have P′ /^{∈} P, so x /^{∈} A and neither x nor b is special. By Lemma 3.3, therefore, P′ is trivial, i.e. b = x /^{∈} A. The edge e of J that ends in b is therefore in E, and hence lies on a lonely path. The final segment of this lonely path that starts at b (with e as its first edge) is again a lonely path, because e ^{∈} E[J]. □

Lemma 3.6. The vertex a does not lie on a lonely path.

Proof. If a ^{∈} A_{2}, then a is popular by definition, so being on—and hence starting—a lonely path would imply a ^{∈} S. If a ^{∈} A_{1} and a lies on a lonely path, then this path uses the edge of J starting at a. Then { a } is a component of K, and hence a trivial path in W_{0} and in W, giving a ^{∈} T. □

Let x be the last vertex of P that is not on any lonely path, and let y be the vertex following x on P. Let L be a lonely path containing y. Then

(3.7) x /^{∈} L, and xyL is not a lonely path.

Since y /^{∈} T, y can only be in V [J] if the edge of J ending in y is in E. (Recall that L must use an edge of J incident with y, and apply Lemma 3.3.) We may therefore make the following assumption:

(3.8) If y ^{∈} V [J], then L starts at y (with the edge of J that ends in y).

Lemma 3.9. The vertex y is popular.

Proof. If y is not popular, then xyL can fail to be a lonely path only if it fails to be an alternating path. By (3.7) and (3.8), this can happen only if x ^{∈} V [J] and xyL fails to start with an edge of J. But x /^{∈} B, so x has a successor q on Q(x). By (3.7) and (3.8), we have q ≠ y. Now qxyL is a lonely path (possibly containing q twice) that contradicts the choice of x. □

Let z be the last popular vertex on P. Then z ≠ b, because b is unpopular by Lemma 3.5. As z ^{∈} yP by Lemma 3.9, the choice of x and definition of y imply that z lies on some lonely path. But then z ^{∈} V [J], say z ^{∈} Q ^{∈} J: otherwise the final segment of this lonely path that starts at z would again be lonely, and the popularity of z would mean that z ^{∈} S. Let q be the vertex following z on Q, and let t be the vertex following z on P.

Lemma 3.10. zq /^{∈} E.

Proof. Let p be the vertex preceding z on Q. (This exists, since z ≠ a.) If zq ^{∈} E, then pz /^{∈} E: otherwise z would be not only popular but special, giving { z } ^{∈} P and z ^{∈} T. But if pz /^{∈} E, then zq ^{∈} E implies by Lemma 3.3 that z ^{∈} T, a contradiction. □

Since t ^{∈} yP, there is a lonely path M containing t. As with y in (3.8), we may assume the following:

(3.11) If t ^{∈} V [J], then M starts at t (with the edge of J that ends in t).

By Lemma 3.10, zq is not an edge of M. By (3.11), this means that t ≠ q; in particular, zq and zt are distinct edges. Moreover, zt is not an edge of M, since then M would have to use its starting edge again. Therefore, qztM is an alternating path. Since t is not popular (by the choice of z), this means that qztM is even a lonely path. (Note that zt is a ‘real’ edge, not the reverse of a J -edge, so the popularity of z does not prevent this path from being lonely.) This, however, contradicts Lemma 3.10, completing the proof of Lemma 1.

4. Consequences

In this section we apply Lemma 1 to deduce some concrete partial results towards Erdős’s conjecture. First, we need another lemma.

Lemma 4.1. Let κ be an infinite cardinal. If Erdős’s conjecture holds for all graphs of order ⩽ κ, then it holds for all webs Γ = (G, A, B) such that |A|, |B| ⩽ κ.

Proof. Let Γ = (G, A, B) be a web with |A|, |B| ⩽ κ, and assume the conjecture holds for every graph of order ⩽ κ. Let G′ be obtained from G by adding all edges xy such that G contains a set of > κ independent x–y paths (i.e. paths that are disjoint except in x and y). To prove the conjecture for Γ, it suffices to find an orthogonal paths/separator pair (P, S) for Γ′ := (G′, A, B). Indeed, then S is clearly also an A–B separator in G. As for the paths in P, their foreign edges can be replaced inductively by paths in G whose interiors avoid each other and all the paths in P (since |P| ⩽ κ), giving an A–B warp in G. We thus obtain an orthogonal pair for Γ.

Let G′′ be the union of all minimal A–B paths in G′. (A path P = a … b is minimal if G′ contains no a–b path Q with V (Q) ⫋ V (P).) It is now sufficient to find an orthogonal paths/separator pair for Γ′′ = (G′′, A, B), which will clearly also be an orthogonal pair for Γ′. It thus suffices to show that |G′′| ⩽ κ.

Suppose |G′′| > κ, and consider a set X ⊆ V (G′′)∖(A∪B) of size > κ, say X = { x_{β} | β < α }. (Recall that |A|, |B| ⩽ κ by assumption.) For each β < α, use the definition of G′′ to find a minimal A–B path P_{β} in G′ containing x_{β}. For all β < α, define inductively P′_{β} as the maximal final segment of P_{β}x_{β} that meets ⋃_{γ<β} P′_{γ} at most in its starting vertex s_{β}. Since |A| ⩽ κ, there is a vertex s ^{∈} G′′ such that s = s_{β} for every β in some set Δ ⊆ α of size > κ. Then F_{1} := ⋃_{β^{∈}Δ} sP_{β}x_{β} is a fan from s onto Y := { x_{β}|β ^{∈} Δ }.

Similarly, ⋃_{β^{∈}Δ} x_{β}P_{β} contains a fan F_{2} from some set Z ⊆ Y of size > κ to a vertex t. Clearly, F_{2} may be chosen so that no two of its paths meet a common path of F_{1}. It is then easy to combine F_{1} and F_{2} into a set of > κ independent s–t paths in G′′. Thus st is an edge of G′, by definition of G′. But s and t are non-consecutive vertices on some common path P_{β} (take any β such that x_{β} ^{∈} Z), which contradicts the minimality of P_{β}. □

Combining Lemma 1 and Lemma 4.1, we can now easily prove the following.

Theorem 4.2. Let κ be an infinite cardinal. If Erdős’s conjecture holds for all graphs of order ⩽ κ, then it holds for all webs Γ = (G, A, B) such that |A| ⩽ κ.

Proof. Let Γ = (G, A, B) be a web with |A| ⩽ κ. Let \overleftarrow{W} be a wave in \overleftarrow{Γ} such that \overleftarrow{Γ′} := \overleftarrow{Γ}/\overleftarrow{W} has no non-trivial wave. Let B′ := ter [\overleftarrow{W}], and let H ⊆ G be such that \overleftarrow{Γ′} = (\overleftarrow{H}, B′, A). (In other words, take the underlying graph of \overleftarrow{Γ′}, reverse its edges, and call the resulting graph H.) Since \overleftarrow{Γ′} is unhindered, we have |B′| ⩽ |A| ⩽ κ by Lemma 1. Now if the conjecture holds for all graphs of size ⩽ κ, then by Lemma 4.1 it holds for \overleftarrow{Γ′}, and there is a warp \overleftarrow{J} in \overleftarrow{Γ′} together with a B′–A separator S in \overleftarrow{H} consisting of a choice of one vertex from each path in \overleftarrow{J}. But S is also a B–A separator in \overleftarrow{G} (because ter [\overleftarrow{W}] is one) and hence an A–B separator in G. Thus S, together with J followed by a suitable subset of W, is an orthogonal paths/separator pair for Γ. □

Corollary 4.3. Erdős’s conjecture is valid for all webs Γ = (G, A, B) in which A is countable.

Proof. By Theorem 4.2 and the fact that the conjecture holds for countable graphs [ 2 ]. □

Not surprisingly, Corollary 4.3 on its own does not need the full strength of Lemma 1. In fact, with hindsight, it is not too difficult to deduce the corollary directly from the main result of [ 3 ].

We conclude this section with an application of Lemma 1 to webs that come with a partial linkage.

Theorem 4.4. Let Γ = (G, A, B) be a web, and assume that G contains an A–B warp J such that A\in [J] is countable. Then Erdős’s conjecture holds for Γ.

Proof. As in the proof of Theorem 4.2, we let \overleftarrow{W} be a wave in \overleftarrow{Γ} such that \overleftarrow{Γ′} := \overleftarrow{Γ}/\overleftarrow{W} has no non-trivial wave. Let B′ := ter [\overleftarrow{W}], and let H ⊆ G be such that \overleftarrow{Γ′} = (\overleftarrow{H}, B′, A). Then \overleftarrow{Γ′} is unhindered, and the final segments in \overleftarrow{H} of the paths in \overleftarrow{J} form a B′–A warp \overleftarrow{J′} in \overleftarrow{H}. By Lemma 1, we have

|B′\in [\overleftarrow{J′}]| ⩽ |A\ter [\overleftarrow{J′}]| = |A\in [J]| ⩽ ℵ_{0}.

But such unhindered ‘countable-like’ webs as \overleftarrow{Γ′} are linkable [ 3 ]L̇et \overleftarrow{L} be a B′–A linkage in \overleftarrow{H}. The concatenations of the paths in L with their unique extensions in W then form an A–B warp in Γ, and B′ is an A–B separator in G consisting of a choice of one vertex from each path in this warp. □

References

[ [ 1 ]] R. Aharoni, König’s duality theorem for infinite bipartite graphs, J. London Math. Soc.

29 (1984), 1–12. [ [ 2 ]] R. Aharoni, Menger’s theorem for countable graphs, J. Combin. Theory B 43 (1987),

303–313. [ [ 3 ]] R. Aharoni, Linkability in countable-like webs, in: (G. Hahn et al., Eds.) Cycles and

Rays, NATO ASI Ser. C, Kluwer Academic Publishers, Dordrecht 1990. [ [ 4 ]] R. Aharoni, Infinite matching theory, in: (R. Diestel, Ed.) Directions in Infinite Graph

Theory and Combinatorics, Topics in Discrete Mathematics 3 (1992), North Holland. [ [ 5 ]] D. König, Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesell-

schaft, Leipzig 1936 (reprinted: Chelsea, New York 1950).

Ron Aharoni

Department of Mathematics Technion Haifa 32000 Israel Reinhard Diestel Mathematical Institute Oxford University Oxford OX1 3LB England