A proof of the Erdős-Menger conjecture for countably connected graphs without large simplices

Reinhard Diestel

Erdős conjectured the following infinite version of Menger’s theorem: if two vertices s, t of a graph G are non-adjacent, then G contains a set P of independent s–t paths and an s–t vertex separator X such that X consists of exactly one vertex from each path in P. We prove this conjecture for the case where P is at most countable and G contains no subdivision of an uncountable complete graph. This extends Aharoni’s result that the conjecture holds for all countable graphs.

The following conjecture, due to Erdős, is considered by many to be the top-ranking open problem in infinite graph theory:

Conjecture. If G is an infinite graph and s, t ^{∈} V (G) are non-adjacent, then there exist a set P of independent s–t paths in G and an s–t separator X = { x_{P} | P ^{∈} P } ⊂ V (G) such that x_{P} ^{∈} P \{ s, t } for each P ^{∈} P.

(Two or more paths are independent if their interiors are disjoint.)

This conjecture generalizes Menger’s theorem for finite graphs. It was proved by Aharoni [ 2 ] for countable G, and by Aharoni [ 1 ] for bipartite G of any cardinality. The general case remains open; see Aharoni [ 3 ] for an excellent up-to-date survey on results related to the conjecture.

The purpose of this note is to prove the conjecture for the case when any set of disjoint s–t paths in G is countable (for the particular choice of s and t featuring in the conjecture) and G contains no subdivision of an uncountable complete graph. This extends Aharoni’s countable theorem, but we shall use that result in our proof.

The proof uses simplicial decompositions of graphs. A detailed account of the theory of simplicial decompositions—as well as proofs of the three lemmas stated below—can be found in [ 4 ], but we shall briefly list the few terms needed here. Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family F = (B_{λ})_{λ<σ} is called a simplicial decomposition of G if the following three conditions hold:

(S1) G = ⋃_{λ<σ} B_{λ}; (S2) every subgraph S_{μ} := B_{μ} ∩ ⋃_{λ<μ} B_{λ} is complete (0 < μ < σ); (S3) no S_{μ} contains B_{μ} or any other B_{λ} (0 ≤ λ < μ < σ).

Note that, by (S3), the B_{λ} are distinct for different λ, so F is essentially just a well-ordered set.

For each vertex v ^{∈} G, let λ(v) denote the smallest λ < σ such that v ^{∈} B_{λ}. For example, if s ^{∈} S_{μ} and v ^{∈} B_{μ}\S_{μ}, then λ(s) < μ = λ(v).

Let us recursively define a partial ordering ≤ on F, as follows. Assume that, for a given μ < σ, we have defined ≤ on all pairs (B_{λ}, B_{λ′}) with λ, λ′ < μ. For each λ < μ, set B_{λ} < B_{μ} if B_{λ} ≤ B_{λ(s)} for some s ^{∈} S_{μ}; otherwise let B_{λ} and B_{μ} be incomparable. Notice that B_{λ} < B_{λ′} implies λ < λ′, so ≤ is antisymmetric; the transitivity of ≤ is clear by induction on μ.

It is not difficult to show—see [ 4 ]—that the poset (F, ≤) is a well-founded order-theoretical tree: any strictly decreasing sequence in (F, ≤) is finite, every subset of the form { B′ | B′ ≤ B } is a chain, and B_{0} is its unique minimal element. (F, ≤) will be called a decomposition tree of G and denoted by T_{F}.

For each B ^{∈} T_{F}, let us set B^{−} = ⋃ { B′ | B′ ≤ B } and call B^{−} the shadow of B in T_{F}. The following easy lemma from [ 5 ] says that shadows cannot be much bigger than the factors B themselves:

Lemma 1. If κ is a regular cardinal and every B ^{∈} F has order < κ, then evey shadow in T_{F} has order < κ.

Let us call a subgraph H of G convex if H contains every induced path in G whose endvertices are in H. This implies that H is separation invariant in the following sense: if s, t ^{∈} V (H) and X ⊂ V (H), then X separates s from t in H if and only if X separates s from t in G.

It is shown in [ 5 ] that if F is a simplicial decomposition of G then any subtree of T_{F} induces a convex subgraph of G. In particular:

Lemma 2. For any two factors B_{1}, B_{2} ^{∈} F, the union B_{1}^{−} ∪ B_{2}^{−} of their shadows in T_{F} is convex in G.

We need one more lemma. If κ is an infinite cardinal, let the κ-closure [ G]_{κ} of G be obtained from G by joining any two non-adjacent vertices which can be linked by a set of κ independent paths. (It is not difficult to show that this is indeed a closure operation, i.e. that [ [ G]_{κ}]_{κ} = [ G]_{κ}.) A theorem of Halin [ 6 ] says that if κ > ℵ_{0} is regular and [ G]_{κ} contains no K_{κ} subgraph (where K_{κ} denotes the complete graph on κ vertices), then [ G]_{κ} admits a simplicial decomposition into factors of order < κ. Moreover, Halin [ 6 ] shows that [ G]_{κ} contains a subdivided K_{κ} if and only if G does; in particular, if G contains no subdivided K_{κ} then [ G]_{κ} ⊅ K_{κ}. We thus have the following:

Lemma 3. If G contains no subdivided uncountable complete graph, then [ G]_{ℵ_{1}} has a simplicial decomposition into countable factors.

We are now ready for the proof of our theorem.

Theorem. Erdős’s infinite Menger conjecture is true in the case where any set of disjoint s–t paths in G is countable and G contains no subdivision of an uncountable complete graph.

Proof. Apply Lemma 3 to obtain a simplicial decomposition F = (B_{λ})_{λ<σ} of [ G]_{ℵ_{1}} into countable factors. Note that s and t are still non-adjacent in [ G]_{ℵ_{1}}, by the definition of [ G]_{ℵ_{1}} and our assumption on the countable linkability of s and t in G.

Let H = B_{λ(s)}^{−} ∪ B_{λ(t)}^{−}, the shadows being taken in T_{F}. By Lemma 2, H is convex in [ G]_{ℵ_{1}}, and by Lemma 1, H is countable. By Aharoni’s theorem, therefore, H contains a (countable) set P of independent s–t paths and an s–t separator X consisting of one vertex from the interior of each path in P.

Since H is convex in [ G]_{ℵ_{1}}, the set X separates s and t even in [ G]_{ℵ_{1}}, and therefore in G. Let us modify the paths of P ^{∈} P to paths P′ ⊂ G, by replacing their ‘new’ edges (i.e. those that are edges of [ G]_{ℵ_{1}} but not original edges of G) with suitable independent paths in G. Let E be the union of the edge sets of the paths in P. Then E is countable, say E = { e_{1}, e_{2}, … }. Let the endvertices of e_{n} be denoted by x_{n} and y_{n}. For each n in turn, replace e_{n} with an x_{n}–y_{n} path P_{n} ⊂ G whose interior avoids H and all the paths P_{i} with i < n; by definition of e_{n} and [ G]_{ℵ_{1}}, there is an uncountable set of independent x_{n}–y_{n} paths in G to choose from, so P_{n} can always be found as desired.

It is then clear that these modified paths P′ form a set P′ of independent s–t paths in G. Moreover, since V (P) ⊂ V (P′) for each P ^{∈} P, the set X again consists of exactly one vertex from each of the paths in P′, as required. □

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, Infinite matching theory, in: (R. Diestel, Ed.) Directions in Infinite Graph Theory and Combinatorics,

Annals of Discrete Mathematics, in press. [ 4 ] R. Diestel, Graph Decompositions—a study in infinite graph theory, Oxford University Press, Oxford 1990. [ 5 ] R. Diestel, The structure of TK_{a}-free graphs, J. Combin. Theory B (to appear). [ 6 ] R. Halin, Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl, Abh. Math. Sem.

Univ. Hamburg 31 (1967), 156–165.