The depth-first search tree structure of TK_{ℵ_{0}}-free graphs

Reinhard Diestel

We characterize the graphs containing no subdivided infinite complete graph by their normal, or depth-first search, tree structure. This implies, but is more explicit and intuitive than, the recent result of Robertson, Seymour and Thomas that these are precisely the graphs of finite tree-width.

1. Introduction

A rooted subtree T of a graph G is called normal if the endvertices of any edge of G are comparable in the natural tree order ⩽_{T} of T, where t ⩽_{T} t′ if t lies on the path in T between t′ and the root. (In other words, the edges of G run along branches of T but never across. For a finite graph, any subtree of G obtained by depth-first search has this property.) Countable graphs [ 7 ] and TK_{ℵ_{0}}-free graphs [ 6 ] (those not containing a subgraph isomorphic to a TK_{ℵ_{0}}, a subdivided infinite complete graph) have normal spanning trees if they are connected, but arbitrary graphs need not. (Weaker versions of normal spanning trees that exist for arbitrary graphs, but which retain much of the strength of the original concept, are studied in [ 1 ].) For many types of infinite graph problems it is useful to have normal spanning trees available, and to know as much as possible about their particular embeddings; see [ 4 ] or [ 5 ] for a demonstration of the power of this tool.

The purpose of this note is to draw attention to a characterization of the TK_{ℵ_{0}}-free graphs in terms of their normal spanning trees. This characterization will follow without much difficulty from known results about these trees, but seems to have eluded the attention of researchers in the field (including the author). The structural description it gives is substantially more detailed than the best ‘known’ characterization of the TK_{ℵ_{0}}-free graphs by their tree structure, due to Robertson, Seymour and Thomas [ 8 ], which will follow as an easy corollary.

2. The characterization theorem

Let G be a graph with a normal spanning tree T, and let R be a ray (a oneway infinite path) in T. A vertex v ^{∈} G is called a neighbour of R (in G) if G contains an infinite set of v–R paths that are pairwise disjoint except for v.

Theorem. The following two assertions are equivalent for connected graphs G.

(i) G ⊉ TK_{ℵ_{0}}, that is, G contains no subdivided infinite complete graph as a subgraph;

(ii) G has a normal spanning tree T such that any ray in T has only finitely many neighbours.

A graph is said to have finite tree-width if it admits a tree decomposition (T, (X_{t})_{t^{∈}T}) (in the usual sense) of finite width, i.e. one whose factors X_{t} are finite and which satisfies

| ⋃_{j⩾1} ⋂_{i⩾j} X_{t_{i}} | < ∞

for every ray t_{1}t_{2} … in T. Robertson, Seymour and Thomas [ 8 ] proved the following, a result easily recovered from our theorem:

Corollary. A graph is TK_{ℵ_{0}}-free if and only if it has finite tree-width.

(See [ 1–3, 8 ] for similar characterizations of the TK_{κ}-free graphs for uncountable cardinals κ, or [ 9 ] for an impressive overview of these and other related results.)

Before we prove our theorem, let us see how it implies the non-trivial ‘only if’ direction of the corollary. Let G be a TK_{ℵ_{0}}-free graph. Since finite width tree-decompositions of the components of G can easily be combined into a single tree-decomposition of finite width (add an empty root X_{0}), we may assume that G is connected. Let T be a normal spanning tree of G as in the theorem. The sets

X_{t} = { t′ ⩽_{T} t | t′ has a neighbour t′′ ⩾_{T} t }

form a finite width tree-decomposition (T, (X_{t})_{t^{∈}T}) of G.

3. Proof of the theorem

The proof of our theorem will follow easily from Halin’s result that TK_{ℵ_{0}}- free connected graphs have normal spanning trees, together with two simple observations about such trees from [ 5 ].

The first of these observations follows easily from the definition of normality:

(3.1) If T is a normal spanning tree of G, and if t_{1}, t_{2} ^{∈} T are incomparable in ⩽_{T}, then the finite set

{ t | t <_{T} t_{1} and t <_{T} t_{2} }

separates t_{1} from t_{2} in G.

As a consequence of (3.1), we see that if R is a ray in T starting at the root, and v ^{∈} G is a neighbour of R, then v ^{∈} R.

Moreover, we have the following [ 4, Lemma 3.11 ]:

(3.2) If a ray R ⊆ T has infinitely many neighbours in G, then G ⊇ TK_{ℵ_{0}}.

Observation (3.2) immediately implies the forward direction of our theorem. For the backward direction note that, by (3.1), the vertices of infinite degree in any TK_{ℵ_{0}} would be pairwise comparable with respect to ⩽_{T}. They would thus lie on a common ray in T and be neighbours of this ray. This completes the proof of the theorem.

References

[ [ 1 ]] J.M. Brochet und R. Diestel, Normal tree orders for infinite graphs, Trans. Amer. Math.

Soc. (to appear). [ [ 2 ]] R. Diestel, Graph decompositions: a study in infinite graph theory, Oxford University

Press, Oxford 1990. [ [ 3 ]] R. Diestel, The structure of TK_{a}-free graphs, J. Combin. Theory B 54 (1992), 222–238. [ [ 4 ]] R. Diestel, The classification of finitely spreading graphs, submitted. [ [ 5 ]] R. Diestel and I. Leader, A proof of the bounded graph conjecture, Invent. math. 108

(1992), 131–162. [ [ 6 ]] R. Halin, Simplicial decompositions of infinite graphs, in: (B. Bollobás, Ed.) Advances

in Graph Theory (Annals of Discrete Mathematics 3), North-Holland Publ. Co., Amsterdam/London 1978.

[ [ 7 ]] H. A. Jung, Wurzelbäume und unendliche Wege in Graphen, Math. Nachr. 41 (1969),

1–22. [ [ 8 ]] N. Robertson, P. D. Seymour and R. Thomas, Excluding infinite clique subdivisions,

Trans. Amer. Math. Soc. (to appear). [ [ 9 ]] N. Robertson, P. D. Seymour and R. Thomas, Excluding infinite minors, in: (R. Diestel,

Ed.) Directions in Infinite Graph Theory and Combinatorics (Topics in Discrete Mathematics 3), North-Holland Publ. Co., Amsterdam/London 1992.

Reinhard Diestel, Faculty of Mathematics (SFB 343), Bielefeld University, P.O. Box 8640, D-4800 Bielefeld, Germany.