Journal of Graph Theory
Early View
ARTICLE
Open Access

Counterexamples Regarding Linked and Lean Tree-Decompositions of Infinite Graphs

Sandra Albrechtsen, 

Corresponding Author

Sandra Albrechtsen

Department of Mathematics, University of Hamburg, Hamburg, Germany

Correspondence: Sandra Albrechtsen ([email protected])

Search for more papers by this author
Raphael W. Jacobs, 

Raphael W. Jacobs

Department of Mathematics, University of Hamburg, Hamburg, Germany

Search for more papers by this author
Paul Knappe, 

Paul Knappe

Department of Mathematics, University of Hamburg, Hamburg, Germany

Search for more papers by this author
Max Pitz, 

Max Pitz

Department of Mathematics, University of Hamburg, Hamburg, Germany

Search for more papers by this author
First published: 15 July 2025
https://doi.org/10.1002/jgt.23279

ABSTRACT

Kříž and Thomas showed that every (finite or infinite) graph of tree-width k ∈ N $k\in {\mathbb{N}}$ admits a lean tree-decomposition of width k $k$ . We discuss a number of counterexamples demonstrating the limits of possible generalisations of their result to arbitrary infinite tree-width. In particular, we construct a locally finite, planar, connected graph that has no lean tree-decomposition.

1 Introduction

1.1 Lean Tree-Decompositions

A cornerstone in both Robertson and Seymour's work [1] on well-quasi-ordering finite graphs, and in Thomas's result [2] that the class of infinite graphs of tree-width < k $\lt k$ is well-quasi-ordered under the minor relation for all k ∈ N $k\in {\mathbb{N}}$ , is Kříž and Thomas's result on lean tree-decompositions. Recall that a tree-decomposition ( T , ( V t ) t ∈ T ) $(T,{({V}_{t})}_{t\in T})$ is lean if for every two (not necessarily distinct) nodes s , t ∈ T $s,t\in T$ and sets of vertices Z s ⊆ V s ${Z}_{s}\subseteq {V}_{s}$ and Z t ⊆ V t ${Z}_{t}\subseteq {V}_{t}$ with ∣ Z s ∣ = ∣ Z t ∣ = : ℓ ∈ N $| {Z}_{s}| =| {Z}_{t}| =:\ell \in {\mathbb{N}}$ , either G $G$ contains ℓ $\ell $ pairwise disjoint Z s ${Z}_{s}$ – Z t ${Z}_{t}$ paths or there exists an edge e = x y ∈ s T t $e=xy\in sTt$ whose corresponding adhesion set V e ≔ V x ∩ V y ${V}_{e}:= {V}_{x}\cap {V}_{y}$ has size less than ℓ $\ell $ .

Theorem 1.1. ((Thomas [[3]] and Kříž and Thomas [[4]]))For every k ∈ N $k\in {\mathbb{N}}$ , every (finite or infinite) graph of tree-width < k $\lt k$ has a lean tree-decomposition of width < k $\lt k$ .

Is it possible to generalise Theorem 1.1 from finite k $k$ to arbitrary infinite cardinalities? In the following, let κ $\kappa $ be an infinite cardinal. A graph G $G$ has tree-width < κ $\lt \kappa $ if it admits a tree-decomposition of width < κ $\lt \kappa $ , that is, one into parts of size < κ $\lt \kappa $ . A graph G $G$ of tree-width < ℵ 0 $\lt {\aleph }_{0}$ , that is, with a tree-decomposition into finite parts, is said to have finite tree-width. The following questions arise naturally:
  • i.

    Does every graph of tree-width < κ $\lt \kappa $ admit a lean tree-decomposition of width < κ $\lt \kappa $ ? In particular, does every graph of finite tree-width admit a lean tree-decomposition into finite parts?

  • ii.

    If not, does every infinite graph at least admit a lean tree-decomposition?

Note that even without the width restriction, Question (ii) remains nontrivial as the leanness-property has to be satisfied within each bag, which means that we cannot take the trivial tree-decomposition into a single part unless the graph is infinitely connected. Still, our main example shows that the answers to these questions are in the negative:

Example 1.There is a planar, locally finite, connected graph that admits no lean tree-decomposition.

Every locally finite, connected graph is countable, and thus has tree-width < ℵ 0 $\lt {\aleph }_{0}$ : given an arbitrary enumeration { v i : i ∈ N } $\{{v}_{i}:i\in {\mathbb{N}}\}$ of a countable graph G $G$ , assigning to each vertex r i ${r}_{i}$ of a ray R = r 0 r 1 … $R={r}_{0}{r}_{1}\ldots $ the bag V r i ≔ { v 0 , … , v i } ${V}_{{r}_{i}}:= \{{v}_{0},\ldots ,{v}_{i}\}$ yields a ray- and thus also tree-decomposition ( R , V ) $(R,{\mathscr{V}})$ of G $G$ into finite parts. Hence, the graph from Example 1 witnesses that the answers to both questions (i) and (ii) are in the negative.

On the positive side, we provide in [5, Theorem 3] a sufficient criterion that guarantees the existence of a lean tree-decomposition into finite parts:

Theorem 1.2.Every graph without half-grid minor admits a lean tree-decomposition into finite parts.

Note that excluding the half-grid as a minor is sufficient but not necessary for the existence of lean tree-decompositions into finite parts: The countably infinite clique K ℵ 0 ${K}^{{\aleph }_{0}}$ contains the half-grid even as a subgraph but also the above-described ray-decomposition of any given countable graph G $G$ into finite parts is lean for G = K ℵ 0 $G={K}^{{\aleph }_{0}}$ .

As the graph from Example 1 is planar, it has no K 5 ${K}^{5}$ minor, and thus no K ℵ 0 ${K}^{{\aleph }_{0}}$ minor. Hence, in terms of excluded minors, the gap between our positive result Theorem 1.2 and our negative result Example 1 is quite narrow. Nevertheless, it remains open to exactly characterise the graphs, which admit a lean tree-decomposition (into finite parts, or more generally, of width < κ $\lt \kappa $ ).

1.2 Linked Tree-Decompositions

Since the answers to questions (i) and (ii) are in the negative, it is natural to ask what happens if we weaken the condition that the tree-decomposition be lean. One possible such weakening is suggested by the “linkedness”-property, which was extensively studied in [6, 7]: We say a tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ of a graph G $G$ is
  • ◇ $&#9671;$

    strongly linked if for every two nodes s ≠ t $s\ne t$ of T $T$ , there are min { ∣ V e ∣ : e ∈ E ( s T t ) } $\min \{| {V}_{e}| :e\in E(sTt)\}$ pairwise disjoint V s ${V}_{s}$ − V t ${V}_{t}$ paths in G $G$ .

One may further weaken “strongly linked” by requiring the existence of disjoint V s ${V}_{s}$ − V t ${V}_{t}$ paths only between nodes s , t ∈ T $s,t\in T$ that are “comparable”. For this, recall that given a tree T $T$ rooted at a node r $r$ , its tree-order is given by s ⩽ t $s\leqslant t$ for nodes s , t $s,t$ of T $T$ if s $s$ lies on the (unique) path r T t $rTt$ from r $r$ to t $t$ . Thomas [2] defined a rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ of a graph G $G$ to be
  • ◇ $&#9671;$

    linked if for every two comparable nodes s < t $s\lt t$ of the rooted tree T $T$ , there are min { ∣ V e ∣ : e ∈ E ( s T t ) } $\min \{| {V}_{e}| :e\in E(sTt)\}$ pairwise disjoint V s ${V}_{s}$ − V t ${V}_{t}$ paths in G $G$ .

These weakenings of the “leanness”-property are motivated by the fact that for the aforementioned applications of Theorem 1.1 by Robertson and Seymour [1] and by Thomas [2] it is only important that the rooted tree-decomposition is linked.

So what happens if we replace the condition lean in (i) and (ii) by strongly linked or linked? As the trivial tree-decomposition into a single part is always strongly linked, and thus every graph has a strongly linked tree-decomposition, only the weakened version of (i), but not of (ii), is interesting:
  • iii.

    Does every graph of tree-width < κ $\lt \kappa $ admit a strongly linked tree-decomposition of width < κ $\lt \kappa $ ?

However, question (iii) is trivially true for all infinite cardinalities κ $\kappa $ : By definition, every graph G $G$ of tree-width < κ $\lt \kappa $ admits a tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ of width < κ $\lt \kappa $ . Choose an arbitrary root r $r$ of T $T$ . By assigning to each of the nodes t $t$ of T $T$ the bag V t ′ ≔ ⋃ s ∈ r T t V s ${V}_{t}^{^{\prime} }:= {\bigcup }_{s\in rTt}{V}_{s}$ , we obtain a (rooted) tree-decomposition ( T , V ′ ) $(T,{{\mathscr{V}}}^{^{\prime} })$ of width < κ $\lt \kappa $ that is strongly linked; albeit for the trivial reason that s ≠ t ∈ T $s\ne t\in T$ implies V s ′ ∩ V t ′ = V u ′ ${V}_{s}^{^{\prime} }\cap {V}_{t}^{^{\prime} }={V}_{u}^{^{\prime} }$ where u $u$ is the ⩽ $\leqslant $ -minimal node in s T t $sTt$ .

But this tree-decomposition is not useful in practice, and so one would like to have some additional properties making the tree-decomposition less redundant. Especially linked rooted tree-decompositions into finite parts, which are additionally “tight” and “componental”, turned out to be a powerful tool (cf. [5, Sections 1.2–1.4] and [8]; see paragraph after Theorem 1.3 for more details). Given a rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ of a graph G $G$ and an edge e $e$ of T $T$ , we call the subgraph G ↑ ˚ e $G\mathring{\uparrow }e$ of G $G$ induced on ⋃ t ∈ T e V t \ V e ${\bigcup }_{t\in {T}_{e}}{V}_{t}\backslash {V}_{e}$ the part strictly above e $e$ , where T e ${T}_{e}$ is the unique component of T − e $T-e$ that does not contain the root of T $T$ . Then, ( T , V ) $(T,{\mathscr{V}})$ is
  • ◇ $&#9671;$

    componental if all the parts G ↑ ˚ e $G\mathring{\uparrow }e$ strictly above edges e ∈ E ( T ) $e\in E(T)$ are connected, and

  • ◇ $&#9671;$

    tight if for every edge e ∈ E ( T ) $e\in E(T)$ , there is some component C $C$ of G ↑ ˚ e $G\mathring{\uparrow }e$ such that N G ( C ) = V e ${N}_{G}(C)={V}_{e}$ .

We remark that the above strongly linked (rooted) tree-decomposition ( T , V ′ ) $(T,{{\mathscr{V}}}^{^{\prime} })$ is componental if ( T , V ) $(T,{\mathscr{V}})$ was componental; but even if ( T , V ) $(T,{\mathscr{V}})$ was tight, ( T , V ′ ) $(T,{{\mathscr{V}}}^{^{\prime} })$ may no longer be tight.

The property tight ensures that the adhesion sets contain no “unnecessary” vertices. Any given componental rooted tree-decomposition can easily be transformed into a tight and componental rooted tree-decomposition by deleting for every edge e $e$ of T $T$ the nonneighbours of G ↑ ˚ e $G\mathring{\uparrow }e$ in V e ${V}_{e}$ from every V t ${V}_{t}$ with t ∈ T e $t\in {T}_{e}$ . While this construction obviously does not increase the width, it does not necessarily maintain the property (strongly) linked. So, it is natural to strengthen (iii) to ask whether there exists a tree-decomposition, which has all three properties:
  • iv.

    Does every graph of tree-width < κ $\lt \kappa $ admit a tight and componental rooted tree-decomposition of width < κ $\lt \kappa $ that is strongly linked?

  • v.

    If not, does every graph of tree-width < κ $\lt \kappa $ admit a tight and componental rooted tree-decomposition of width < κ $\lt \kappa $ that is at least linked?

The answer to Question (iv) is in the negative already for κ = ℵ 0 $\kappa ={\aleph }_{0}$ , as witnessed by the same graph that we constructed for Example 1:

Example 2.There is a planar, locally finite, connected graph, which admits no tight, componental rooted tree-decomposition into finite parts that is strongly linked.

Question (v), however, has an affirmative answer for κ = ℵ 0 $\kappa ={\aleph }_{0}$ [5, Theorem 1]:

Theorem 1.3.Every graph of finite tree-width admits a rooted tree-decomposition into finite parts that are linked, tight, and componental.

We remark that (v) remains open for uncountable cardinalities κ > ℵ 0 $\kappa \gt {\aleph }_{0}$ . If the answer is positive, one might, as a next step, also strengthen the notion of linked from just considering sizes to a structural notion that encapsulates the typical desired behaviour of infinite path families between two sets, as given by Menger's theorem for infinite graphs [9, Theorem 1.6] proven by Aharoni and Berger.

It turns out that linked rooted tree-decompositions into finite parts, which are additionally tight and componental, as given by Theorem 1.3, are particularly useful (cf. [5, Sections 1.2–1.4] and [8]): In [5, Section 3], we show that rooted tree-decompositions into finite parts, which are linked, tight, and componental display the end structure of the underlying graph. This not only resolves a question of Halin [10, Section 6] but also allows us to deduce from Theorem 1.3, by means of short and unified proofs, the characterisations due to Robertson, Seymour and Thomas of graphs without half-grid minor [11, Theorem 2.6], and of graphs without binary tree subdivision [12, (1.5)]. Also the proof of Theorem 1.2 in [5, Section 8] heavily relies on post-processing the tree-decomposition from Theorem 1.3. Besides these, there are more applications of rooted tree-decomposition into finite parts which are linked, tight, and componental in [5, Section 1.4] and [8].

In fact, we show in [5, Theorem 1′] a more detailed version of Theorem 1.3 which, among others, yields that the adhesion sets of the tree-decomposition intersect “not more than necessary”. We also give an example which proves that this property is best possible even for locally finite graphs (see Section 5 for details).

In light of Question (v) being true for κ = ℵ 0 $\kappa ={\aleph }_{0}$ , one may ask whether a similar modification could rescue (i) for κ = ℵ 0 $\kappa ={\aleph }_{0}$ : What happens if we relax the condition lean in (i) to a corresponding “rooted” version?
  • vi.

    Does every graph of finite tree-width admit a rooted tree-decomposition into finite parts that satisfies the property of being lean for all comparable nodes s ⩽ t $s\leqslant t$ of T $T$ ?

However, the answer to this question is again in the negative, as there is a graph of finite tree-width such that all its tree-decompositions into finite parts violate the “leanness”-property within a single bag:

Example 3.There is a countable graph G $G$ such that every tree-decomposition of G $G$ into finite parts has a bag V t ${V}_{t}$ , which violates the property of being lean for s = t $s=t$ .

We remark that we do not know whether every tree-decomposition, which satisfies the “leanness”-property for every two comparable nodes, must already be lean.

1.3 How This Paper Is Organised

In Section 2, we recall some important definitions and facts about ends and their interplay with tree-decompositions. In Section 3, we prove Examples 1 and 2, and in Section 4, we prove Example 3. Finally, in Section 5, we discuss whether it is possible to strengthen Theorem 1.3 so that the adhesion sets of the tree-decomposition are “upwards” disjoint.

2 Preliminaries

We refer the reader to [5, Section 2] for all the relevant definitions. Besides that, our notation and definitions follow [13]. In particular, the neighbourhood N G ( X ) ${N}_{G}(X)$ of a set X $X$ of vertices in a graph G $G$ is the set of all vertices in V ( G ) \ X $V(G)\backslash X$ that are neighbours of some x ∈ X $x\in X$ . For the convenience of the reader, we recall the ones that are most important in this paper.

Let ( T , V ) $(T,{\mathscr{V}})$ be a rooted tree-decomposition of a graph G $G$ . Given an edge e = t 1 t 2 $e={t}_{1}{t}_{2}$ of T $T$ with t 1 < T t 2 ${t}_{1}{\lt }_{T}{t}_{2}$ , we let T i ${T}_{i}$ be the component of T − e $T-e$ containing t i ${t}_{i}$ for i = 1 , 2 $i=1,2$ . We abbreviate the sides of its induced separation by G ↓ e ≔ G [ ⋃ t ∈ T 1 V t ] $G\downarrow e:= G[{\bigcup }_{t\in {T}_{1}}{V}_{t}]$ and G ↑ e ≔ G [ ⋃ t ∈ T 2 V t ] $G\uparrow e:= G[{\bigcup }_{t\in {T}_{2}}{V}_{t}]$ . Further, we write G ↓ ˚ e ≔ G ↓ e − V e $G\mathring{\downarrow }e:= G\downarrow e-{V}_{e}$ and G ↑ ˚ e ≔ G ↑ e − V e $G\mathring{\uparrow }e:= G\uparrow e-{V}_{e}$ . It is easy to see that G ↑ e ⊇ G ↑ f , G ↑ ˚ e ⊇ G ↑ ˚ f , G ↓ e ⊆ G ↓ f $G\uparrow e\supseteq G\uparrow f,G\mathring{\uparrow }e\supseteq G\mathring{\uparrow }f,G\downarrow e\subseteq G\downarrow f$ , and G ↓ ˚ e ⊆ G ↓ ˚ f $G\mathring{\downarrow }e\subseteq G\mathring{\downarrow }f$ for every two edges e , f ∈ E ( T ) $e,f\in E(T)$ with e ⩽ T f ${e\leqslant }_{T}f$ and also ⋂ e ∈ R G ↑ ˚ e = ∅ ${\bigcap }_{e\in R}G\mathring{\uparrow }e=\varnothing $ for every rooted ray R $R$ in T $T$ .

An end ε $\varepsilon $ of a graph G $G$ is an equivalence class of rays in G $G$ where two rays are equivalent if for every finite set X $X$ they have a tail in the same component of G − X $G-X$ . We refer to this component of G − X $G-X$ as C G ( X , ε ) ${C}_{G}(X,\varepsilon )$ . Write Ω ( G ) ${\rm{\Omega }}(G)$ for the set of all ends of G $G$ . Note that for every end ε $\varepsilon $ of G $G$ and every set X $X$ of vertices of G $G$ , which meets every ε $\varepsilon $ -ray at most finitely often, there is a unique component of G − X $G-X$ that contains a tail of every ε $\varepsilon $ -ray. We refer to this component as C G ( X , ε ) ${C}_{G}(X,\varepsilon )$ , which coincides with the above definition for finite X $X$ .

A vertex v $v$ of G $G$ dominates an end ε $\varepsilon $ of G $G$ if it lies in C G ( X , ε ) ${C}_{G}(X,\varepsilon )$ for every finite set X $X$ of vertices other than v $v$ . We remark that locally finite graphs have no dominating vertices. We denote the set of all vertices of G $G$ , which dominate an end ε $\varepsilon $ by Dom ( ε ) $\text{Dom}(\varepsilon )$ . The degree deg ( ε ) $\text{deg}(\varepsilon )$ of an end ε $\varepsilon $ of G $G$ is the supremum over all cardinals κ $\kappa $ such that there exists a set of κ $\kappa $ pairwise disjoint rays in ε $\varepsilon $ , and its combined degree is Δ ( ε ) ≔ deg ( ε ) + ∣ Dom ( ε ) ∣ ${\rm{\Delta }}(\varepsilon ):= \text{deg}(\varepsilon )+| \text{Dom}(\varepsilon )| $ .

Given a rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ of G $G$ , an end ε $\varepsilon $ of G $G$ gives rise to a rooted ray R $R$ in T $T$ if every ε $\varepsilon $ -ray meets every bag V t ${V}_{t}$ with t ∈ R $t\in R$ at most finitely often, and for every e = s t ∈ T $e=st\in T$ with s < t $s\lt t$ , we have C G ( V s , ε ) ⊆ G ↑ ˚ e ${C}_{G}({V}_{s},\varepsilon )\subseteq G\mathring{\uparrow }e$ . Note that if such a ray exists, then it is unique, and we denote it by R ε ${R}_{\varepsilon }$ . Moreover, if every ray in an end ε $\varepsilon $ of G $G$ meets every bag of a tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ at most finitely often, then ε $\varepsilon $ gives rise to a ray in T $T$ . If the bags of a rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ meet all rays in G $G$ at most finitely often, the above yields a map φ : Ω ( G ) → Ω ( T ) , ε ↦ R ε $\varphi :{\rm{\Omega }}(G)\to {\rm{\Omega }}(T),\varepsilon \mapsto {R}_{\varepsilon }$ . Such a rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$
  • ◇ $&#9671;$

    displays the ends of G $G$ if φ $\varphi $ is a bijection [14],

  • ◇ $&#9671;$

    displays all dominating vertices if liminf e ∈ E ( R ε )   V e = Dom ( ε ) ${\text{liminf}}_{e\in E({R}_{\varepsilon })}\unicode{x0200A}{V}_{e}=\text{Dom}(\varepsilon )$ for all ε ∈ Ω ( G ) $\varepsilon \in {\rm{\Omega }}(G)$ , and

  • ◇ $&#9671;$

    displays all combined degrees if liminf e ∈ E ( R ε ) ∣ V e ∣ = Δ ( ε ) ${\text{liminf}}_{e\in E({R}_{\varepsilon })}| {V}_{e}| ={\rm{\Delta }}(\varepsilon )$ for all ε ∈ Ω ( G ) $\varepsilon \in {\rm{\Omega }}(G)$ .

Moreover, we recall the following lemma [5, Lemma 3.3]:

Lemma 2.1.Let ( T , V ) $(T,{\mathscr{V}})$ be a linked rooted tree-decomposition of a graph G $G$ , which has finite adhesion. Suppose that an end ε $\varepsilon $ of G $G$ gives rise to a ray in T $T$ , which arises from no other end of G $G$ and that liminf e ∈ R   V e = Dom ( ε ) ${\text{liminf}}_{e\in R}\unicode{x0200A}{V}_{e}=\text{Dom}(\varepsilon )$ . Then, liminf e ∈ R ∣ V e ∣ = Δ ( ε ) ${\text{liminf}}_{e\in R}| {V}_{e}| ={\rm{\Delta }}(\varepsilon )$ .

The following lemma follows immediately from [5, Lemmas 3.1–3.3]:

Lemma 2.2.Let ( T , V ) $(T,{\mathscr{V}})$ be a rooted tree-decomposition of a graph G $G$ , which has finite adhesion and which is linked, tight, and componental. Then, ( T , V ) $(T,{\mathscr{V}})$ displays all ends of G $G$ , their dominating vertices, and their combined degrees.

3 Examples 1 and 2—Negative Answers to Questions (i), (ii) and (iv)

In this section, we explain Examples 1 and 2, which we restate here for convenience:

Example 1.There is a planar, locally finite, connected graph that admits no lean tree-decomposition.

Example 2.There is a planar, locally finite, connected graph, which admits no tight, componental rooted tree-decomposition into finite parts that are strongly linked.

Details are in the caption following the image
Figure 1
Open in figure viewerPowerPoint
Depicted is the graph G $G$ from Construction 3.1. The subgraph induced by the orange edges is G 2 ${G}_{2}$ together with the extensions of its horizontal rays. [Color figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
Figure 2
Open in figure viewerPowerPoint
Depicted is the situation in the proof of Lemma 3.2 for n = 2 $n=2$ . [Color figure can be viewed at wileyonlinelibrary.com]

For our proofs of Examples 1 and 2, we construct a graph G $G$ in Construction 3.1 and then show that G $G$ is already as desired for both Examples 1 and 2. The graph in this construction is inspired by [15, Example 7.4].

Construction 3.1.Let G $G$ be the graph depicted in Figure 1. Formally, let G ′ ${G}^{^{\prime} }$ be the graph on the vertex set V ( G ′ ) ≔ { ( i / 2 j , j ) ∣ j ∈ N , 0 ⩽ i ⩽ 2 j + 1 } $V({G}^{^{\prime} }):= \{(i/{2}^{j},j)| j\in {\mathbb{N}},0\leqslant i\leqslant {2}^{j+1}\}$ and with edges between ( i / 2 j , j ) $(i/{2}^{j},j)$ and ( ( i + 1 ) / 2 j , j ) $((i+1)/{2}^{j},j)$ , between ( i / 2 j , j ) $(i/{2}^{j},j)$ and ( i / 2 j , j + 1 ) $(i/{2}^{j},j+1)$ , and also between ( i / 2 j , j ) $(i/{2}^{j},j)$ and ( ( 2 i − 1 ) / 2 j + 1 , j + 1 ) $((2i-1)/{2}^{j+1},j+1)$ for i ⩽ 2 j $i\leqslant {2}^{j}$ (this is the black subgraph in Figure 1). Note that G ′ ${G}^{^{\prime} }$ has a unique end, which we denote by ε $\varepsilon $ .

For every n ∈ N ⩾ 1 $n\in {{\mathbb{N}}}_{\geqslant 1}$ , let G n ≔ N ⩾ 1 □ P 2 n + 1 + 2 n + 1 ${G}_{n}:= {{\mathbb{N}}}_{\geqslant 1}\square {P}_{{2}^{n+1}+{2}^{n}+1}$ be a grid with 2 n + 1 + 2 n + 2 ${2}^{n+1}+{2}^{n}+2$ rows and infinitely many columns. Then, G n ${G}_{n}$ is one-ended and its end ε n ${\varepsilon }_{n}$ has degree 2 n + 1 + 2 n + 2 ${2}^{n+1}+{2}^{n}+2$ . Now the graph G $G$ is obtained from G ′ ⊔ ⊔ n ∈ ℕ G n ${G}^{^{\prime} }\bigsqcup {\bigsqcup }_{n\in {\rm{{\mathbb{N}}}}}{G}_{n}$ by deleting for every n ∈ N $n\in {\mathbb{N}}$ the edge { ( 2 , n ) , ( 2 , n + 1 ) } $\{(2,n),(2,n+1)\}$ of G ′ ${G}^{^{\prime} }$ , identifying the vertices ( 2 , n ) , ( 2 , n + 1 ) $(2,n),(2,n+1)$ of G ′ ${G}^{^{\prime} }$ with the respective vertices ( 1 , 1 ) $(1,1)$ and ( 1 , 2 n + 1 + 2 n + 2 ) $(1,{2}^{n+1}+{2}^{n}+2)$ of G n ${G}_{n}$ , and by extending the horizontal rays in G n ${G}_{n}$ , as indicated in Figure 1. In particular, the extended horizontal rays of each G n ${G}_{n}$ are still disjoint and their initial vertices are precisely U n ≔ { ( i / 2 j , j ) ∣ j ∈ { n , n + 1 } , 2 j ⩽ i ⩽ 2 j + 1 } ${U}_{n}:= \{(i/{2}^{j},j)| j\in \{n,n+1\},{2}^{j}\leqslant i\leqslant {2}^{j+1}\}$ . To get a graph that is not only locally finite but also planar, we subdivide the edges between ( i / 2 n , n ) $(i/{2}^{n},n)$ and ( i / 2 n , n + 1 ) $(i/{2}^{n},n+1)$ with i > 2 n $i\gt {2}^{n}$ in G ′ ${G}^{^{\prime} }$ to obtain the extended rays. For later use, we refer to the vertex set { ( i , j ) ∣ 1 ⩽ j ⩽ 2 n + 1 + 2 n + 2 } $\{(i,j)| 1\leqslant j\leqslant {2}^{n+1}+{2}^{n}+2\}$ in G n ${G}_{n}$ as the i $i$ th column of G n ${G}_{n}$ (indicated in pink in Figure 1 is the first column of G 2 ${G}_{2}$ ) and also set

S n ≔ { ( i / 2 n + 1 , n + 1 ) ∣ 2 n + 1 < i ⩽ 2 n + 2 } ∪ { ( 1 , j ) ∣ 0 ⩽ j ⩽ n + 1 } ${S}_{n}:= \{(i/{2}^{n+1},n+1)| {2}^{n+1}\lt i\leqslant {2}^{n+2}\}\cup \{(1,j)| 0\leqslant j\leqslant n+1\}$
for all n ∈ N $n\in {\mathbb{N}}$ (indicated in purple in Figure 2). This completes the construction.

In the remainder of this section, we prove that graph G $G$ from Construction 3.1 is as desired for Examples 1 and 2. For this, we first show two auxiliary lemmas. The first says that G $G$ does not admit a tree-decomposition, which “efficiently distinguishes” all ends of G $G$ . Recall that in a tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ of G $G$ every edge e = t 0 t 1 $e={t}_{0}{t}_{1}$ of T $T$ induces a separation as follows: For i = 0 , 1 $i=0,1$ , write T i ${T}_{i}$ for the component of T − e $T-e$ that contains t i ${t}_{i}$ . Then, { ⋃ s ∈ T 0 V s , ⋃ s ∈ T 1 V s } $\{{\bigcup }_{s\in {T}_{0}}{V}_{s},{\bigcup }_{s\in {T}_{1}}{V}_{s}\}$ is a separation of G $G$ [13, Lemma 12.3.1]. A separation { A , B } $\{A,B\}$ of G $G$ efficiently distinguishes two ends ε , ε ′ $\varepsilon ,{\varepsilon }^{^{\prime} }$ of G $G$ if ε $\varepsilon $ and ε ′ ${\varepsilon }^{^{\prime} }$ live in components of G − ( A ∩ B ) $G-(A\cap B)$ on different sides of { A , B } $\{A,B\}$ , and there is no separation { C , D } $\{C,D\}$ of G $G$ of smaller order ∣ C ∩ D ∣ $| C\cap D| $ with this property. A tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ distinguishes two ends ε , ε ′ $\varepsilon ,{\varepsilon }^{^{\prime} }$ of G $G$ efficiently if some edge e $e$ of T $T$ induces a separation, which efficiently distinguishes ε $\varepsilon $ and ε ′ ${\varepsilon }^{^{\prime} }$ .

Lemma 3.2.Let ( T , V ) $(T,{\mathscr{V}})$ be a tree-decomposition of the graph from Construction 3.1. Then, there exists n ∈ N $n\in {\mathbb{N}}$ such that ( T , V ) $(T,{\mathscr{V}})$ does not efficiently distinguish ε n ${\varepsilon }_{n}$ and ε $\varepsilon $ .

Proof.Suppose towards a contradiction that G $G$ admits a tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ such that, for every end ε n ${\varepsilon }_{n}$ of G $G$ , there exists an edge f n ${f}_{n}$ such that the separation induced by f n ${f}_{n}$ distinguishes ε n ${\varepsilon }_{n}$ and ε $\varepsilon $ efficiently. Then, V f n ${V}_{{f}_{n}}$ has a size at most 2 n + 1 + n + 2 ${2}^{n+1}+n+2$ as witnessed by S n ${S}_{n}$ (indicated in purple in Figure 2). By the definition of G ′ ${G}^{^{\prime} }$ , there are in fact ∣ S n ∣ $| {S}_{n}| $ disjoint ε $\varepsilon $ − ε n ${\varepsilon }_{n}$ double rays R i n ${R}_{i}^{n}$ in G $G$ (indicated in orange in Figure 2), so every sizewise-minimal ε $\varepsilon $ − ε n ${\varepsilon }_{n}$ separator, and in particular V f n ${V}_{{f}_{n}}$ , has to meet each R i n ${R}_{i}^{n}$ precisely once. In particular, ∣ V f n ∣ = ∣ S n ∣ $| {V}_{{f}_{n}}| =| {S}_{n}| $ and hence f n ≠ f m ${f}_{n}\ne {f}_{m}$ for all n ≠ m ∈ N $n\ne m\in {\mathbb{N}}$ . Moreover, V f n ${V}_{{f}_{n}}$ avoids the ε $\varepsilon $ -ray R = ( 0 , 0 ) ( 0 , 1 ) … $R=(0,0)(0,1)\,\ldots $ (indicated in blue in Figure 2) and the vertex ( 2 , 0 ) $(2,0)$ , as they are both disjoint from all the ε $\varepsilon $ − ε n ${\varepsilon }_{n}$ double rays R i n ${R}_{i}^{n}$ . Thus, G − V f n $G-{V}_{{f}_{n}}$ has a component C n ${C}_{n}$ that contains R $R$ and a component C n ′ ${C}_{n}^{^{\prime} }$ that contains ( 2 , 0 ) $(2,0)$ . In particular, ε $\varepsilon $ lives in C n ${C}_{n}$ . Since there is an ε n ${\varepsilon }_{n}$ -ray (indicated in green in Figure 2), which starts in ( 2 , 0 ) $(2,0)$ and is disjoint from the R i n , ε n ${R}_{i}^{n},{\varepsilon }_{n}$ lives in C n ′ ${C}_{n}^{^{\prime} }$ . As V f n ${V}_{{f}_{n}}$ separates ε $\varepsilon $ and ε n ${\varepsilon }_{n}$ , we have C n ≠ C n ′ ${C}_{n}\ne {C}_{n}^{^{\prime} }$ . Thus, ( 0 , 0 ) $(0,0)$ and ( 2 , 0 ) $(2,0)$ lie on different sides of the separation induced by f n ${f}_{n}$ .

Let V t ${V}_{t}$ and V s ${V}_{s}$ be some bags of ( T , V ) $(T,{\mathscr{V}})$ , which contain ( 0 , 0 ) $(0,0)$ and ( 2 , 0 ) $(2,0)$ , respectively. Since the separations induced by every f n ${f}_{n}$ separate ( 0 , 0 ) $(0,0)$ and ( 2 , 0 ) $(2,0)$ , all the infinitely many distinct edges f n ${f}_{n}$ lie on the finite path t T s $tTs$ , which is a contradiction. □ $\square $

The next lemma essentially says that every tree-decomposition of G $G$ that displays all ends of G $G$ and their combined degrees cannot be strongly linked.

Lemma 3.3.Let ( T , V ) $(T,{\mathscr{V}})$ be a rooted tree-decomposition of the graph G $G$ from Construction 3.1. Suppose that every end ω $\omega $ of G $G$ gives rise to a rooted ray R ω ${R}_{\omega }$ in T $T$ with liminf e ∈ R ω   V e = ∅ ${\text{liminf}}_{e\in {R}_{\omega }}\unicode{x0200A}{V}_{e}=\varnothing $ and liminf e ∈ R ω ∣ V e ∣ = deg ( ω ) ${\text{liminf}}_{e\in {R}_{\omega }}| {V}_{e}| =\text{deg}(\omega )$ . Then, ( T , V ) $(T,{\mathscr{V}})$ is not strongly linked.

Proof.Suppose towards a contradiction that ( T , V ) $(T,{\mathscr{V}})$ is strongly linked. Let n ∈ N $n\in {\mathbb{N}}$ be arbitrary. We write R n ${R}_{n}$ for the rooted ray R ε n ${R}_{{\varepsilon }_{n}}$ in T $T$ , which arose from ε n ${\varepsilon }_{n}$ . Since ( T , V ) $(T,{\mathscr{V}})$ is a tree-decomposition, for every ray R $R$ of T $T$ , we have ⋂ e ∈ R V ( G ↑ ˚ e ) = ∅ ${\bigcap }_{e\in R}V(G\mathring{\uparrow }e)=\varnothing $ , and thus for every finite vertex set W $W$ of G $G$ , all but finitely many edges e $e$ of R $R$ have the property that G ↑ ˚ e $G\mathring{\uparrow }e$ avoids W $W$ . In particular, for all but finitely many edges e $e$ of R n ${R}_{n}$ , the part G ↑ ˚ e $G\mathring{\uparrow }e$ avoids the first and second column of G n ${G}_{n}$ . As liminf e ∈ R n ∣ V e ∣ = deg ( ε n ) ${\text{liminf}}_{e\in {R}_{n}}| {V}_{e}| =\text{deg}({\varepsilon }_{n})$ , we may choose such an edge e n ∈ R n ${e}_{n}\in {R}_{n}$ so that ∣ V e n ∣ = deg ( ε n ) $| {V}_{{e}_{n}}| =\text{deg}({\varepsilon }_{n})$ and every later edge e $e$ on R n ${R}_{n}$ satisfies ∣ V e ∣ ⩾ ∣ V e n ∣ $| {V}_{e}| \geqslant | {V}_{{e}_{n}}| $ . Since G ↑ ˚ e n $G\mathring{\uparrow }{e}_{n}$ avoids the first column of G n ${G}_{n}$ , the component D n ${D}_{n}$ of G ↑ ˚ e n $G\mathring{\uparrow }{e}_{n}$ in which ε n ${\varepsilon }_{n}$ lives is contained in G n ${G}_{n}$ .

We claim that G ↑ ˚ e n $G\mathring{\uparrow }{e}_{n}$ contains all but finitely many vertices of G n ${G}_{n}$ , and N G ( D n ) = V e n ${N}_{G}({D}_{n})={V}_{{e}_{n}}$ . Indeed, the rows of G n ${G}_{n}$ are pairwise disjoint ε n ${\varepsilon }_{n}$ -rays. Since ε n ${\varepsilon }_{n}$ lives in D n ${D}_{n}$ , the component D n ${D}_{n}$ contains a tail of each row of G n ${G}_{n}$ . As the rows of G n ${G}_{n}$ cover the entire G n ${G}_{n}$ , the part G ↑ ˚ e n ⊇ D n $G\mathring{\uparrow }{e}_{n}\supseteq {D}_{n}$ contains all but finitely many vertices of G n ${G}_{n}$ . Since D n ⊆ G ↑ ˚ e n ${D}_{n}\subseteq G\mathring{\uparrow }{e}_{n}$ avoids the first column of G n ${G}_{n}$ , its neighbourhood N G ( D n ) ⊆ V e n ${N}_{G}({D}_{n})\subseteq {V}_{{e}_{n}}$ contains at least one vertex of each row. Since there are deg ( ε n ) $\text{deg}({\varepsilon }_{n})$ rows, we have ∣ N G ( D n ) ∣ ⩾ deg ( ε n ) = ∣ V e n ∣ $| {N}_{G}({D}_{n})| \geqslant \text{deg}({\varepsilon }_{n})=| {V}_{{e}_{n}}| $ , and thus, N G ( D n ) = V e n ${N}_{G}({D}_{n})={V}_{{e}_{n}}$ .

As N G ( D n ) = V e n ${N}_{G}({D}_{n})={V}_{{e}_{n}}$ and D n ${D}_{n}$ is connected, G ↑ e n $G\uparrow {e}_{n}$ is connected. It follows that G ↑ e n $G\uparrow {e}_{n}$ is a subgraph of G n ${G}_{n}$ and avoids the first column of G n ${G}_{n}$ , since G ↑ ˚ e n $G\mathring{\uparrow }{e}_{n}$ meets G n ${G}_{n}$ and avoids the first and second column of G n ${G}_{n}$ .

Let H n ${H}_{n}$ be the component of G − S n $G-{S}_{n}$ that contains G 0 ${G}_{0}$ (where S n ${S}_{n}$ is the set indicated in purple in Figure 2). We claim that there is an edge e n ′ ${e}_{n}^{^{\prime} }$ of the rooted ray R ε ${R}_{\varepsilon }$ in T $T$ , which arose from ε $\varepsilon $ , such that ∣ V e n ′ ∣ ⩾ deg ( ε n ) $| {V}_{{e}_{n}^{^{\prime} }}| \geqslant \text{deg}({\varepsilon }_{n})$ and such that G ↑ e $G\uparrow e$ avoids H n ${H}_{n}$ . For this, we note that the rays R m ${R}_{m}$ are distinct from R ε ${R}_{\varepsilon }$ , since liminf e ∈ R m ∣ V e ∣ = deg ( ε m ) ${\text{liminf}}_{e\in {R}_{m}}| {V}_{e}| =\text{deg}({\varepsilon }_{m})$ is finite but liminf e ∈ R ε ∣ V e ∣ = deg ( ε ) ${\text{liminf}}_{e\in {R}_{\varepsilon }}| {V}_{e}| =\text{deg}(\varepsilon )$ is infinite. Hence, we may choose a tail R ε n ⊆ R ε ${R}_{\varepsilon }^{n}\subseteq {R}_{\varepsilon }$ of R ε ${R}_{\varepsilon }$ that avoids all rays R m ${R}_{m}$ for m ⩽ n $m\leqslant n$ . Since all R m ${R}_{m}$ and also R ε ${R}_{\varepsilon }$ are rooted at the same vertex of T $T$ , every edge e $e$ of R ε n ${R}_{\varepsilon }^{n}$ satisfies ( G ↑ e ) ∩ ( G ↑ ˚ e m ) = ∅ $(G\uparrow e)\cap (G\mathring{\uparrow }{e}_{m})=\varnothing $ . As G ↑ ˚ e m $G\mathring{\uparrow }{e}_{m}$ contains all but finitely many vertices of G m ${G}_{m}$ for m ⩽ n $m\leqslant n$ , the set W n ≔ V ( H n ) \ ( ⋃ m ⩽ n V ( G ↑ ˚ e n ) ) ${W}_{n}:= V({H}_{n})\backslash ({\bigcup }_{m\leqslant n}V(G\mathring{\uparrow }{e}_{n}))$ is finite. Since ( T , V ) $(T,{\mathscr{V}})$ is a tree-decomposition, for all but finitely many edges e $e$ of R ε n ${R}_{\varepsilon }^{n}$ , the part G ↑ ˚ e $G\mathring{\uparrow }e$ avoids W n ${W}_{n}$ and hence H n ${H}_{n}$ . Note that, for each edge e $e$ of R ε n ${R}_{\varepsilon }^{n}$ , its adhesion set V e ${V}_{e}$ avoids G ↑ ˚ e m $G\mathring{\uparrow }{e}_{m}$ for every m ⩽ n $m\leqslant n$ . Since liminf e ∈ R ε n   V e = ∅ ${\text{liminf}}_{e\in {R}_{\varepsilon }^{n}}\unicode{x0200A}{V}_{e}=\varnothing $ and W n ${W}_{n}$ is finite, for all but finitely many edges e $e$ of R ε n ${R}_{\varepsilon }^{n}$ , the adhesion set V e ${V}_{e}$ avoids the finite set W n ${W}_{n}$ . Thus, for all but finitely many edges e $e$ of R ε ${R}_{\varepsilon }$ , the part G ↑ e $G\uparrow e$ avoids H n ${H}_{n}$ . Finally, since liminf e ∈ R ε ∣ V e ∣ = deg ( ε ) ${\text{liminf}}_{e\in {R}_{\varepsilon }}| {V}_{e}| =\text{deg}(\varepsilon )$ is infinite, we may choose an edge e n ′ ${e}_{n}^{^{\prime} }$ of R ε ${R}_{\varepsilon }$ so that G ↑ e n ′ $G\uparrow {e}_{n}^{^{\prime} }$ avoids H n ${H}_{n}$ and ∣ V e n ′ ∣ ⩾ deg ( ε n ) $| {V}_{{e}_{n}^{^{\prime} }}| \geqslant \text{deg}({\varepsilon }_{n})$ .

Recall that the adhesion set V e n ${V}_{{e}_{n}}$ is contained in G n ${G}_{n}$ but avoids the first column of G n ${G}_{n}$ , and thus, V e n ⊆ V ( H n ) ${V}_{{e}_{n}}\subseteq V({H}_{n})$ . Since also V e n ′ ∩ V ( H n ) = ∅ ${V}_{{e}_{n}^{^{\prime} }}\cap V({H}_{n})=\varnothing $ , there are at most 2 n + 1 + n + 2 ${2}^{n+1}+n+2$ pairwise disjoint V e n ${V}_{{e}_{n}}$ − V e n ′ ${V}_{{e}_{n}^{^{\prime} }}$ paths in G $G$ , as witnessed by S n ${S}_{n}$ . As ( T , V ) $(T,{\mathscr{V}})$ is strongly linked by assumption, there is an edge f n ${f}_{n}$ on the unique e n ${e}_{n}$ − e n ′ ${e}_{n}^{^{\prime} }$ path in T $T$ such that ∣ V f n ∣ ⩽ ∣ S n ∣ $| {V}_{{f}_{n}}| \leqslant | {S}_{n}| $ . Moreover, V f n ${V}_{{f}_{n}}$ separates V e n ${V}_{{e}_{n}}$ and V e n ′ ${V}_{{e}_{n}^{^{\prime} }}$ , and thus also ε n ${\varepsilon }_{n}$ and ε $\varepsilon $ . By the definition of G ′ ${G}^{^{\prime} }$ , there are in fact ∣ S n ∣ $| {S}_{n}| $ disjoint ε $\varepsilon $ − ε n ${\varepsilon }_{n}$ double rays R i n ${R}_{i}^{n}$ in G $G$ (indicated in orange in Figure 2), and hence, the separation induced by f n ${f}_{n}$ efficiently distinguishes ε $\varepsilon $ and ε n ${\varepsilon }_{n}$ . Since n ∈ N $n\in {\mathbb{N}}$ was chosen arbitrarily, Lemma 3.2 yields the desired contradiction. □ $\square $

Proof of Example 2.The graph G $G$ from Construction 3.1 is planar, locally finite, and connected. By Lemma 2.2, every linked, tight, componental rooted tree-decomposition of G $G$ into finite parts displays all the ends of G $G$ , their dominating vertices, and their (combined) degrees. Thus, Lemma 3.3 ensures that those tree-decompositions are not strongly linked. □ $\square $

We now turn to our proof of Example 1, that is, that graph G $G$ from Construction 3.1 does not admit a lean tree-decomposition. The proof consists of two steps. First, we show in Lemma 3.6 that G $G$ does not admit a lean tree-decomposition into finite parts. Then, we show in Lemma 3.7 that G $G$ neither admits a lean tree-decomposition that has an infinite part.

By definition, every lean tree-decomposition is in particular strongly linked. For the first step, it remains to show that every lean tree-decomposition of G $G$ into finite parts satisfies the premise of Lemma 3.3: it displays all ends of G $G$ and their combined degrees, up to the fact that maybe some rays of the decomposition tree do not arise from an end of G $G$ . In fact, the following Lemma 3.5 together with Lemma 2.1 implies that this holds true for all graphs H $H$ and lean tree-decompositions of them.

To prove Lemma 3.5, we first show that even though lean tree-decompositions may not be componental, they are not far away from it.

Lemma 3.4.Let ( T , V ) $(T,{\mathscr{V}})$ be a rooted tree-decomposition of finite adhesion of a graph H $H$ . Suppose there is an edge e = s t ∈ E ( T ) $e=st\in E(T)$ with s < T t $s{\lt }_{T}t$ and a set Y ⊆ V e $Y\subseteq {V}_{e}$ such that ( H ↑ e ) − Y $(H\uparrow e)-Y$ has at least two components C 1 , C 2 ${C}_{1},{C}_{2}$ . Suppose further that V ( C 1 ) ∩ V e ≠ ∅ $V({C}_{1})\cap {V}_{e}\ne \varnothing $ and V ( C 2 ) ∩ ( V t \ V e ) ≠ ∅ $V({C}_{2})\cap ({V}_{t}\backslash {V}_{e})\ne \varnothing $ . Then, ( T , V ) $(T,{\mathscr{V}})$ is not lean.

Proof.By assumption, we may pick vertices v 1 ∈ V ( C 1 ) ∩ V e ${v}_{1}\in V({C}_{1})\cap {V}_{e}$ and v 2 ∈ V ( C 2 ) ∩ ( V t \ V e ) ${v}_{2}\in V({C}_{2})\cap ({V}_{t}\backslash {V}_{e})$ . Set Z 1 ≔ V e ${Z}_{1}:= {V}_{e}$ and Z 2 ≔ ( V e \ { v 1 } ) ∪ { v 2 } ${Z}_{2}:= ({V}_{e}\backslash \{{v}_{1}\})\cup \{{v}_{2}\}$ . By construction, ∣ Z 1 ∣ = ∣ V e ∣ = ∣ Z 2 ∣ = : k $| {Z}_{1}| =| {V}_{e}| =| {Z}_{2}| =:k$ . Since ( T , V ) $(T,{\mathscr{V}})$ is lean and Z 1 , Z 2 ⊆ V t ${Z}_{1},{Z}_{2}\subseteq {V}_{t}$ , there is a family P ${\mathscr{P}}$ of k $k$ disjoint Z 1 ${Z}_{1}$ − Z 2 ${Z}_{2}$ paths in H $H$ . Note that every path in P ${\mathscr{P}}$ that starts in Z 1 ∩ Z 2 = V e \ { v 1 } ${Z}_{1}\cap {Z}_{2}={V}_{e}\backslash \{{v}_{1}\}$ is a trivial path. Hence, there is a path P ∈ P $P\in {\mathscr{P}}$ that starts in { v 1 } = Z 1 \ Z 2 $\{{v}_{1}\}={Z}_{1}\backslash {Z}_{2}$ and ends in { v 2 } = Z 2 \ Z 1 $\{{v}_{2}\}={Z}_{2}\backslash {Z}_{1}$ . But v 1 ∈ V ( C 1 ) ${v}_{1}\in V({C}_{1})$ is separated from v 2 ∈ V ( C 2 ) \ V e ⊆ V ( H ↑ ˚ e ) ${v}_{2}\in V({C}_{2})\backslash {V}_{e}\subseteq V(H\mathring{\uparrow }e)$ by Y ∪ ( V ( C 2 ) ∩ V e ) ⊆ V e \ { v 1 } $Y\cup (V({C}_{2})\cap {V}_{e})\subseteq {V}_{e}\backslash \{{v}_{1}\}$ . This contradicts that the paths in P ${\mathscr{P}}$ are pairwise disjoint. □ $\square $

Lemma 3.5.Let ( T , V ) $(T,{\mathscr{V}})$ be a rooted tree-decomposition of a graph H $H$ into finite parts, which is lean as an unrooted tree-decomposition. Then, every ray in T $T$ arises from at most one end of H $H$ . Moreover, if a ray R $R$ in T $T$ arises from an end ε $\varepsilon $ of H $H$ , then liminf e ∈ R   V e = Dom ( ε ) ${\text{liminf}}_{e\in R}\unicode{x0200A}{V}_{e}=\text{Dom}(\varepsilon )$ .

Proof.For the first assertion, suppose towards a contradiction that there are two distinct ends ε 1 , ε 2 ${\varepsilon }_{1},{\varepsilon }_{2}$ of H $H$ that give rise to the same rooted ray R $R$ of T $T$ . As ε 1 , ε 2 ${\varepsilon }_{1},{\varepsilon }_{2}$ are distinct, there is a finite set X $X$ of vertices of H $H$ such that ε 1 , ε 2 ${\varepsilon }_{1},{\varepsilon }_{2}$ live in distinct components C 1 , C 2 ${C}_{1},{C}_{2}$ of G − X $G-X$ .

Now pick a vertex v 1 ∈ V ( C 1 ) ${v}_{1}\in V({C}_{1})$ . Since ( T , V ) $(T,{\mathscr{V}})$ is a tree-decomposition, ⋂ e ∈ R V ( H ↑ ˚ e ) = ∅ ${\bigcap }_{e\in R}V(H\mathring{\uparrow }e)=\varnothing $ , and thus all but finitely many edges e $e$ of R $R$ have the property that H ↓ e $H\downarrow e$ contains the finite set X ∪ { v 1 } $X\cup \{{v}_{1}\}$ . As ε 2 ${\varepsilon }_{2}$ gives rise to R $R$ and lives in C 2 ${C}_{2}$ , there is an edge e = s t $e=st$ on R $R$ with s < T t $s{\lt }_{T}t$ such that X ∪ { v 1 } ⊆ H ↓ e $X\cup \{{v}_{1}\}\subseteq H\downarrow e$ and V ( C 2 ) ∩ ( V t \ V e ) $V({C}_{2})\cap ({V}_{t}\backslash {V}_{e})$ is nonempty. Note that V ( C 1 ) ∩ V e $V({C}_{1})\cap {V}_{e}$ is nonempty as C 1 ${C}_{1}$ is connected and meets both H ↓ e $H\downarrow e$ (in the vertex v 1 ${v}_{1}$ ) and H ↑ ˚ e $H\mathring{\uparrow }e$ (as ε 1 ${\varepsilon }_{1}$ gives rise to R $R$ and lives in C 1 ${C}_{1}$ ). Set Y ≔ X ∩ V e $Y:= X\cap {V}_{e}$ and, for i = 1 , 2 $i=1,2$ , let C i ′ ${C}_{i}^{^{\prime} }$ be a component of C i ∩ ( H ↑ e − Y ) ${C}_{i}\cap (H\uparrow e-Y)$ , which contains a vertex from V ( C 1 ) ∩ V e $V({C}_{1})\cap {V}_{e}$ or V ( C 2 ) ∩ ( V t \ V e ) $V({C}_{2})\cap ({V}_{t}\backslash {V}_{e})$ , respectively. Then, Y , C 1 ′ , C 2 ′ $Y,{C}_{1}^{^{\prime} },{C}_{2}^{^{\prime} }$ are as in Lemma 3.4. It follows that ( T , V ) $(T,{\mathscr{V}})$ is not lean, which is a contradiction.

To show the moreover statement, let ε $\varepsilon $ be an end of H $H$ that gives rise to a ray R $R$ in T $T$ . Now suppose towards a contradiction that there is a vertex w ∈ liminf e ∈ R   V e $w\in {\text{liminf}}_{e\in R}\unicode{x0200A}{V}_{e}$ that does not dominate ε $\varepsilon $ . Then, there is a finite set X ⊆ V ( H ) $X\subseteq V(H)$ and distinct components C 1 , C 2 ${C}_{1},{C}_{2}$ of G − X $G-X$ such that w ∈ V ( C 1 ) $w\in V({C}_{1})$ and ε $\varepsilon $ live in C 2 ${C}_{2}$ .

As above, there is an edge e = s t $e=st$ on R $R$ with s < T t $s{\lt }_{T}t$ such that H ↓ e $H\downarrow e$ contains X ∪ { w } $X\cup \{w\}$ and V ( C 2 ) ∩ ( V t \ V e ) $V({C}_{2})\cap ({V}_{t}\backslash {V}_{e})$ is nonempty. Since w $w$ also lies in liminf f ∈ R   V f ${\text{liminf}}_{f\in R}\unicode{x0200A}{V}_{f}$ , we have w ∈ V e $w\in {V}_{e}$ , and thus, V ( C 1 ) ∩ V e $V({C}_{1})\cap {V}_{e}$ is nonempty. As above, we obtain a contradiction by applying Lemma 3.4. □ $\square $

Lemma 3.6.The graph G $G$ from Construction 3.1 admits no lean tree-decomposition into finite parts.

Proof.Suppose towards a contradiction that G $G$ admits a lean tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ into finite parts. It follows from Lemma 3.5 that every end ω $\omega $ of G $G$ gives rise to a ray R ω ${R}_{\omega }$ in T $T$ which arises from no other end of G $G$ . Moreover, we have liminf e ∈ R ω   V e = Dom ( ω ) = ∅ ${\text{liminf}}_{e\in {R}_{\omega }}\unicode{x0200A}{V}_{e}=\text{Dom}(\omega )=\varnothing $ , as locally finite graphs have no dominating vertices. So since ( T , V ) $(T,{\mathscr{V}})$ is lean and hence strongly linked, Lemma 2.1 implies that liminf e ∈ R ω ∣ V e ∣ = Δ ( ω ) = deg ( ω ) ${\text{liminf}}_{e\in {R}_{\omega }}| {V}_{e}| ={\rm{\Delta }}(\omega )=\text{deg}(\omega )$ (because G $G$ is locally finite). Thus, by Lemma 3.3, ( T , V ) $(T,{\mathscr{V}})$ is not strongly linked, which is a contradiction. □ $\square $

For the proof of Example 1 it remains to show that the graph from Construction 3.1 neither admits a lean tree-decomposition with possibly infinite parts.

Lemma 3.7.The graph G $G$ from Construction 3.1 admits no lean tree-decomposition.

Proof.Suppose for a contradiction that G $G$ has a lean tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ . Let T $T$ be rooted in an arbitrary node. We first show that every end ε n ${\varepsilon }_{n}$ gives rise to a ray R n ${R}_{n}$ in T $T$ , that is, every bag of ( T , V ) $(T,{\mathscr{V}})$ meets every ε n ${\varepsilon }_{n}$ -ray at most finitely often. For this, it suffices to show that every bag meets G n ${G}_{n}$ at most finitely often. Let n ∈ N $n\in {\mathbb{N}}$ be given, and suppose there is a bag V t ${V}_{t}$ that contains infinitely many vertices of G n ${G}_{n}$ . Then, let Z 1 ⊆ V t ${Z}_{1}\subseteq {V}_{t}$ be a set of 2 n + 1 + 2 n + 3 ${2}^{n+1}+{2}^{n}+3$ vertices of G n ${G}_{n}$ , and let i ∈ N $i\in {\mathbb{N}}$ such that Z 1 ${Z}_{1}$ is contained in the first i $i$ columns of G n ${G}_{n}$ . Now let Z 2 ⊆ V t ${Z}_{2}\subseteq {V}_{t}$ be a set of 2 n + 1 + 2 n + 3 ${2}^{n+1}+{2}^{n}+3$ vertices of G n ${G}_{n}$ that avoids the first i $i$ columns of G n ${G}_{n}$ . Since the i $i$ th column of G n ${G}_{n}$ has size 2 n + 1 + 2 n + 2 ${2}^{n+1}+{2}^{n}+2$ and separates Z 1 ${Z}_{1}$ and Z 2 ${Z}_{2}$ , this contradicts that ( T , V ) $(T,{\mathscr{V}})$ is lean.

Hence, each ε n ${\varepsilon }_{n}$ -ray meets every bag of ( T , V ) $(T,{\mathscr{V}})$ at most finitely often, which implies that ε n ${\varepsilon }_{n}$ gives rise to a ray R n ${R}_{n}$ in T $T$ . In particular, then, there exists a node t $t$ of R n ${R}_{n}$ such that V t ${V}_{t}$ meets every row of G n ${G}_{n}$ : If not, then every bag V t ${V}_{t}$ of R n ${R}_{n}$ avoids some row of G n ${G}_{n}$ . In fact, since ε n ${\varepsilon }_{n}$ gives rise to R n ${R}_{n}$ and thus every V t ${V}_{t}$ meets every row that meets V s ${V}_{s}$ for some node s < T t $s{\lt }_{T}t$ of R n ${R}_{n}$ , all V t ${V}_{t}$ with t ∈ R n $t\in {R}_{n}$ avoid the same row of G n ${G}_{n}$ . Since ε n ${\varepsilon }_{n}$ gives rise to R n ${R}_{n}$ , it follows that this row is contained in G ↑ ˚ e $G\mathring{\uparrow }e$ for all edges e $e$ of R n ${R}_{n}$ , which contradicts that ( T , V ) $(T,{\mathscr{V}})$ is a tree-decomposition. Hence, there is a node t n ${t}_{n}$ of R n ${R}_{n}$ such that V t n ${V}_{{t}_{n}}$ meets every row of G n ${G}_{n}$ . Let X n ⊆ V t n ${X}_{n}\subseteq {V}_{{t}_{n}}$ be a set consisting of precisely one vertex of each row of G n ${G}_{n}$ . In particular, X n ${X}_{n}$ has size 2 n + 1 + 2 n + 2 ${2}^{n+1}+{2}^{n}+2$ and is linked to ε n ${\varepsilon }_{n}$ .

Since G $G$ admits no lean tree-decomposition into finite parts by Lemma 3.6, ( T , V ) $(T,{\mathscr{V}})$ contains an infinite bag V s ${V}_{s}$ . As shown above, V s ${V}_{s}$ contains at most finitely many vertices of each G n ${G}_{n}$ . Hence, for every n ∈ N $n\in {\mathbb{N}}$ , the bag V s ${V}_{s}$ contains infinitely many vertices of G n ′ ≔ G ′ [ { ( i , j ) ∈ V ( G ′ ) : j > n } ] ∪ ⋃ m > n G m ${G}_{n}^{^{\prime} }:= {G}^{^{\prime} }[\{(i,j)\in V({G}^{^{\prime} }):j\gt n\}]\cup {\bigcup }_{m\gt n}{G}_{m}$ . Let Y n ⊆ V s ${Y}_{n}\subseteq {V}_{s}$ consist of 2 n + 1 + 2 n + 2 ${2}^{n+1}+{2}^{n}+2$ vertices of G n ′ ${G}_{n}^{^{\prime} }$ . Since G $G$ is locally finite and connected, it follows from the Star-Comb Lemma [13, Lemma 8.2.2] that there is a comb C $C$ in G $G$ with teeth in V s ${V}_{s}$ . Recall that the comb C $C$ is the union of a ray R $R$ , its spine, and infinitely many disjoint (possibly trivial) paths with precisely their first vertex in R $R$ and their last vertex in V s ${V}_{s}$ . As V s ∩ V ( G n ) ${V}_{s}\cap V({G}_{n})$ is finite for all n ∈ N $n\in {\mathbb{N}}$ , the spine R $R$ of C $C$ is an ε $\varepsilon $ -ray.

Since X n ⊆ V ( G n ) ${X}_{n}\subseteq V({G}_{n})$ and Y n ⊆ V ( G n ′ ) ${Y}_{n}\subseteq V({G}_{n}^{^{\prime} })$ , there are at most 2 n + 1 + n + 2 ${2}^{n+1}+n+2$ pairwise disjoint X n ${X}_{n}$ − Y n ${Y}_{n}$ paths in G $G$ , as witnessed by S n ${S}_{n}$ (indicated in purple in Figure 2). As ( T , V ) $(T,{\mathscr{V}})$ is lean by assumption, there is an edge f n ${f}_{n}$ on the unique t n ${t}_{n}$ − s $s$ path in T $T$ such that ∣ V f n ∣ ⩽ ∣ S n ∣ $| {V}_{{f}_{n}}| \leqslant | {S}_{n}| $ . Moreover, V f n ${V}_{{f}_{n}}$ separates V t n ${V}_{{t}_{n}}$ and V s ${V}_{s}$ . We claim that V f n ${V}_{{f}_{n}}$ also separates ε n ${\varepsilon }_{n}$ and ε $\varepsilon $ . Indeed, since C $C$ has teeth in V s ${V}_{s}$ , the component D $D$ of G − V f n $G-{V}_{{f}_{n}}$ in which ε $\varepsilon $ lives meets V s \ V f n ${V}_{s}\backslash {V}_{{f}_{n}}$ . Because X n ${X}_{n}$ is linked to ε n ${\varepsilon }_{n}$ and ∣ V f n ∣ ⩽ ∣ S n ∣ < ∣ X n ∣ $| {V}_{{f}_{n}}| \leqslant | {S}_{n}| \lt | {X}_{n}| $ , the component D n ${D}_{n}$ of G − V f n $G-{V}_{{f}_{n}}$ in which ε n ${\varepsilon }_{n}$ lives meets X n \ V f n ⊆ V t n \ V f n ${X}_{n}\backslash {V}_{{f}_{n}}\subseteq {V}_{{t}_{n}}\backslash {V}_{{f}_{n}}$ . Since V f n ${V}_{{f}_{n}}$ separates V t n ${V}_{{t}_{n}}$ and V s ${V}_{s}$ , the components D $D$ and D n ${D}_{n}$ are distinct, that is, V f n ${V}_{{f}_{n}}$ separates ε $\varepsilon $ and ε n ${\varepsilon }_{n}$ . By the definition of G $G$ , there are ∣ S n ∣ $| {S}_{n}| $ disjoint ε $\varepsilon $ − ε n ${\varepsilon }_{n}$ double rays R i n ${R}_{i}^{n}$ in G $G$ , and hence, the separation induced by f n ${f}_{n}$ distinguishes ε $\varepsilon $ and ε n ${\varepsilon }_{n}$ efficiently. Now Lemma 3.2 yields the desired contradiction. □ $\square $

Proof of Example 1.The graph G $G$ from Construction 3.1 is planar, locally finite, and connected. The assertion thus follows from Lemma 3.7. □ $\square $

4 Example 3—Negative Answer to Question (vi)

In this section, we construct Example 3, which we restate here for convenience:

Example 3.There is a countable graph G $G$ such that every tree-decomposition of G $G$ into finite parts has a bag V t ${V}_{t}$ , which violates the property of being lean for s = t $s=t$ .

Details are in the caption following the image
Figure 3
Open in figure viewerPowerPoint
Depicted is the graph G ′ ${G}^{^{\prime} }$ and the set U 4 ${U}_{4}$ in purple from Example 3. Indicated in blue is the ray ( 0 , 2 ) ( 1 , 2 ) … $(0,2)(1,2)\ldots $ that contains the vertex w $w$ and indicated in green is the path ( 0 , 0 ) ( 1 , 0 ) ( 2 , 0 ) ( 3 , 0 ) $(0,0)(1,0)(2,0)(3,0)$ that contains the vertex u $u$ in the case m = 4 $m=4$ . [Color figure can be viewed at wileyonlinelibrary.com]

The graph in this example is essentially the same as [14, Example 3.7].

Proof.Let G ′ ${G}^{^{\prime} }$ be the N × { 0 , 1 , 2 } ${\mathbb{N}}\times \{0,1,2\}$ grid, that is, V ( G ′ ) = { ( i , j ) ∣ i ∈ N , j ∈ { 0 , 1 , 2 } } $V({G}^{^{\prime} })=\{(i,j)| i\in {\mathbb{N}},j\in \{0,1,2\}\}$ , and there is an edge in G ′ ${G}^{^{\prime} }$ between ( i , j ) $(i,j)$ and ( i ′ , j ′ ) $({i}^{^{\prime} },{j}^{^{\prime} })$ whenever ∣ i − i ′ ∣ + ∣ j − j ′ ∣ = 1 $| i-{i}^{^{\prime} }| +| j-{j}^{^{\prime} }| =1$ . For every n ∈ N ⩾ 1 $n\in {{\mathbb{N}}}_{\geqslant 1}$ , let U n ≔ { ( i , 1 ) ∣ i ⩽ n } ∪ { ( n − 1 , 0 ) , ( n , 0 ) } ${U}_{n}:= \{(i,1)| i\leqslant n\}\cup \{(n-1,0),(n,0)\}$ (see Figure 3). Now the graph G $G$ is obtained from G ′ ${G}^{^{\prime} }$ by making the sets U n ${U}_{n}$ complete. We claim that G $G$ is as desired.

Let ( T , V ) $(T,{\mathscr{V}})$ be a rooted tree-decomposition of G $G$ into finite parts. Let R ⊆ T $R\subseteq T$ be the rooted ray arising from the unique end ε $\varepsilon $ of G $G$ . Since ( T , V ) $(T,{\mathscr{V}})$ is a tree-decomposition, we have ⋂ e ∈ R V ( G ↑ ˚ e ) = ∅ ${\bigcap }_{e\in R}V(G\mathring{\uparrow }e)=\varnothing $ , and hence, there is an edge e $e$ of R $R$ such that ( 0 , 0 ) , ( 0 , 1 ) , ( 0 , 2 ) ∈ V ( G ↓ e ) $(0,0),(0,1),(0,2)\in V(G\downarrow e)$ . As ε $\varepsilon $ gives rise to R $R$ , the ray ( 0 , 0 ) ( 1 , 0 ) ( 2 , 0 ) … $(0,0)(1,0)(2,0)\ldots $ through the bottom row has a tail in G ↑ ˚ e $G\mathring{\uparrow }e$ , that is, there is n ∈ N $n\in {\mathbb{N}}$ such that ( n ′ , 0 ) ∈ V ( G ↑ ˚ e ) $({n}^{^{\prime} },0)\in V(G\mathring{\uparrow }e)$ for all n ′ ⩾ n ${n}^{^{\prime} }\geqslant n$ . Since G [ U n ′ ] $G[{U}_{{n}^{^{\prime} }}]$ is complete, it follows that U n ′ ⊆ V ( G ↑ e ) ${U}_{{n}^{^{\prime} }}\subseteq V(G\uparrow e)$ for all n ′ ⩾ n ${n}^{^{\prime} }\geqslant n$ .

Next, observe that there is an edge e ′ > e ${e}^{^{\prime} }\gt e$ of R $R$ such that U n ⊆ V ( G ↓ e ′ ) ${U}_{n}\subseteq V(G\downarrow {e}^{^{\prime} })$ . Now let f = t 1 t 2 $f={t}_{1}{t}_{2}$ with t 1 < T t 2 ${t}_{1}{\lt }_{T}{t}_{2}$ be the ⩽ T ${\leqslant }_{T}$ -minimal edge of R $R$ such that there exists m ∈ N ⩾ n $m\in {{\mathbb{N}}}_{\geqslant n}$ with U m ⊆ V ( G ↓ f ) ${U}_{m}\subseteq V(G\downarrow f)$ . Note that e ′ ${e}^{^{\prime} }$ is a candidate for f $f$ , and observe that e < f $e\lt f$ . Let m $m$ be maximal such that U m ⊆ V ( G ↓ f ) ${U}_{m}\subseteq V(G\downarrow f)$ ; in particular, m ⩾ n $m\geqslant n$ . To see that this maximum exists, note that the ray ( 0 , 0 ) ( 1 , 0 ) ( 2 , 0 ) … $(0,0)(1,0)(2,0)\ldots $ has a tail in G ↑ ˚ f $G\mathring{\uparrow }f$ , and hence, there is i ∈ N $i\in {\mathbb{N}}$ such that ( j , 0 ) ∈ V ( G ↑ ˚ f ) $(j,0)\in V(G\mathring{\uparrow }f)$ for all j ⩾ i $j\geqslant i$ . Thus, m ⩽ i $m\leqslant i$ .

By the choice of f $f$ and m $m$ , we have U m + 1 ⊆ V ( G ↑ f ) ${U}_{m+1}\subseteq V(G\uparrow f)$ , as U m + 1 ${U}_{m+1}$ is complete. Hence, as V f ${V}_{f}$ separates G ↑ ˚ f $G\mathring{\uparrow }f$ and G ↓ ˚ f $G\mathring{\downarrow }f$ , it follows that U m ∩ U m + 1 ⊆ V f ⊆ V t 1 ${U}_{m}\cap {U}_{m+1}\subseteq {V}_{f}\subseteq {V}_{{t}_{1}}$ . Moreover, as ( 0 , 2 ) ∈ V ( G ↓ e ) ⊆ V ( G ↓ f ) $(0,2)\in V(G\downarrow e)\subseteq V(G\downarrow f)$ by the choice of e $e$ , and because ε $\varepsilon $ gives rise to R $R$ , the ray ( 0 , 2 ) ( 1 , 2 ) ( 2 , 2 ) … $(0,2)(1,2)(2,2)\,\ldots $ meets V f ⊆ V t 1 ${V}_{f}\subseteq {V}_{{t}_{1}}$ in a vertex w $w$ . Similarly, the path ( 0 , 0 ) ( 1 , 0 ) … ( m − 1 , 0 ) $(0,0)(1,0)\ldots (m-1,0)$ meets V f ′ ⊆ V t 1 ${V}_{{f}^{^{\prime} }}\subseteq {V}_{{t}_{1}}$ in a vertex u $u$ where f ′ ${f}^{^{\prime} }$ is the unique down-edge at t 1 ${t}_{1}$ . Indeed, we have ( 0 , 0 ) ∈ G ↓ f ′ $(0,0)\in G\downarrow {f}^{^{\prime} }$ by the choice of e < f $e\lt f$ and ( m − 1 , 0 ) ∈ G ↑ f ′ $(m-1,0)\in G\uparrow {f}^{^{\prime} }$ : if ( m − 1 , 0 ) $(m-1,0)$ was contained in G ↓ ˚ f ′ $G\mathring{\downarrow }{f}^{^{\prime} }$ , then U m ⊆ V ( G ↓ f ′ ) ${U}_{m}\subseteq V(G\downarrow {f}^{^{\prime} })$ since U m ${U}_{m}$ is complete in G $G$ , which contradicts the ⩽ T ${\leqslant }_{T}$ -minimal choice of f $f$ .

We now let s ≔ t 1 = : t $s:= {t}_{1}=:t$ and define Z 1 ≔ ( U m ∩ U m + 1 ) ∪ { w } ${Z}_{1}:= ({U}_{m}\cap {U}_{m+1})\cup \{w\}$ and Z 2 ≔ ( U m ∩ U m + 1 ) ∪ { u } ${Z}_{2}:= ({U}_{m}\cap {U}_{m+1})\cup \{u\}$ . By construction, we have ∣ Z 1 ∣ = ∣ Z 2 ∣ = m + 3 $| {Z}_{1}| =| {Z}_{2}| =m+3$ and Z 1 , Z 2 ⊆ V t 1 ${Z}_{1},{Z}_{2}\subseteq {V}_{{t}_{1}}$ . Hence, ( T , V ) $(T,{\mathscr{V}})$ violates the property of being lean for s = t 1 = t $s={t}_{1}=t$ since U m ∩ U m + 1 ${U}_{m}\cap {U}_{m+1}$ separates w $w$ and u $u$ and hence witnesses that G $G$ contains at most m + 2 $m+2$ disjoint Z 1 ${Z}_{1}$ − Z 2 ${Z}_{2}$ paths. □ $\square $

5 Upwards Disjointness of Adhesion Sets

As mentioned in the introduction, we show in [5, Theorem 1′] a more detailed version of Theorem 1.3, which, among others, yields that the adhesion sets of the tree-decomposition intersect “not more than necessary”:

Theorem 5.1.Every graph G $G$ of finite tree-width admits a rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ into finite parts that are linked, tight, and componental. Moreover, we may assume that

  • 1.

    for every e < T e ′ ∈ E ( T ) $e{\lt }_{T}{e}^{^{\prime} }\in E(T)$ with ∣ V e ∣ ⩽ ∣ V e ′ ∣ $| {V}_{e}| \leqslant | {V}_{{e}^{^{\prime} }}| $ , each vertex of V e ∩ V e ′ ${V}_{e}\cap {V}_{{e}^{^{\prime} }}$ either dominates some end of G $G$ that lives in G ↑ e ′ $G\uparrow {e}^{^{\prime} }$ or is contained in a critical vertex set of G $G$ that is included in G ↑ e ′ $G\uparrow {e}^{^{\prime} }$ .

Halin [16, Theorem 2] showed that every locally finite, connected graph has a linked ray-decomposition into finite parts with disjoint adhesion sets. He used this result in [10, Satz 10] to establish Theorem 5.1 for locally finite graphs with at most two ends, replacing (1)with the stronger condition of having disjoint adhesion sets. In light of this, we discuss here that (1) describes how close one may come to having “disjoint adhesion sets” in the general case.

If G $G$ is not locally finite, we generally cannot require the tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ in Theorem 1.3 to have disjoint adhesion sets while having finite parts, as every dominating vertex of an end ε $\varepsilon $ will be eventually contained in all adhesion sets along the ray of T $T$ , which arises from ε $\varepsilon $ . Moreover, as every critical vertex set has to lie in an adhesion set of any tree-decomposition into finite parts, and since the tree-decomposition is linked, one can easily check that the adhesion sets also intersect in critical vertex sets. Thus, one might hope to obtain a tree-decomposition as in Theorem 1.3 that satisfies the following condition:
  • 1′.

    for every e < T e ′ ∈ E ( T ) $e{\lt }_{T}{e}^{^{\prime} }\in E(T)$ , each vertex of V e ∩ V e ′ ${V}_{e}\cap {V}_{{e}^{^{\prime} }}$ either dominates some end of G $G$ that lives in G ↑ e ′ $G\uparrow {e}^{^{\prime} }$ or is contained in a critical vertex set of G $G$ that is included in G ↑ e ′ $G\uparrow {e}^{^{\prime} }$ .

But (1) allows for more than (1′): If e < T e ′ ∈ T $e{\lt }_{T}{e}^{^{\prime} }\in T$ and ∣ V e ∣ > ∣ V e ′ ∣ $| {V}_{e}| \gt | {V}_{{e}^{^{\prime} }}| $ , then V e ${V}_{e}$ and V e ′ ${V}_{{e}^{^{\prime} }}$ are allowed to intersect also in vertices that do not dominate an end and that are not contained in a critical vertex set. The following example shows that allowing this is in fact necessary. It presents a locally finite graph that does not admit a tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ as in Theorem 1.3 with (1′), the stronger version of (1). As locally finite graphs do not have any dominating vertices and critical vertex sets, (1′) boils down to the property that the tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ has upwards disjoint adhesion sets, that is, V e ∩ V e ′ = ∅ ${V}_{e}\cap {V}_{{e}^{^{\prime} }}=\varnothing $ for every e < T e ′ ∈ E ( T ) $e{\lt }_{T}{e}^{^{\prime} }\in E(T)$ .

Example 5.2.There is a locally finite connected graph G $G$ , which does not admit a linked, tight, componental rooted tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ into finite parts with upwards disjoint adhesion sets, that is, one which satisfies (1′).

Details are in the caption following the image
Figure 4
Open in figure viewerPowerPoint
Depicted is the graph G $G$ from Example 5.2. The blue subgraph is induced by the vertices ( S , i , j ) $({\mathfrak{S}},i,j)$ of G $G$ with S = ( 0 , 0 , 0 , … ) ${\mathfrak{S}}=(0,0,0,\ldots )$ . The green subgraphs are induced by the vertices ( S x , i , j ) $({{\mathfrak{S}}}_{x},i,j)$ of G $G$ with S x = ( x , 0 , … ) ${{\mathfrak{S}}}_{x}=(x,0,\ldots )$ for x ∈ N ⩾ 1 $x\in {{\mathbb{N}}}_{\geqslant 1}$ , respectively. [Color figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
Figure 5
Open in figure viewerPowerPoint
A ray in G $G$ that meets all the sets V e S n ${V}_{{e}_{{{\mathscr{S}}}_{n}}}$ . The end to which it belongs has degree 2. [Color figure can be viewed at wileyonlinelibrary.com]

Proof.Let c 00 ( N ) ${c}_{00}({\mathbb{N}})$ denote the set of all sequences with values in N ${\mathbb{N}}$ that are eventually zero. Let c ′ ⊆ c 00 ( N ) ${c}^{^{\prime} }\subseteq {c}_{00}({\mathbb{N}})$ be the set of all the sequences S = ( s n ) n ∈ N ${\mathscr{S}}={({s}_{n})}_{n\in {\mathbb{N}}}$ for which there exists N ∈ N $N\in {\mathbb{N}}$ such that s i ⩾ 1 ${s}_{i}\geqslant 1$ for all i < N $i\lt N$ and s i = 0 ${s}_{i}=0$ for all i ⩾ N $i\geqslant N$ . Let G $G$ be the graph depicted in Figure 4, that is, the graph on the vertex set

V ( G ) ≔ { ( ( s n ) n ∈ N , i , j ) ∈ c ′ × N × { 1 , 2 , 3 } } $V(G):= \{({({s}_{n})}_{n\in {\mathbb{N}}},i,j)\in {c}^{^{\prime} }\times {\mathbb{N}}\times \{1,2,3\}\}$
and with edges between ( S , i , j ) $({\mathscr{S}},i,j)$ and ( S , i ′ , j ′ ) $({\mathscr{S}},{i}^{^{\prime} },{j}^{^{\prime} })$ whenever ∣ i − i ′ ∣ + ∣ j − j ′ ∣ = 1 $| i-{i}^{^{\prime} }| +| j-{j}^{^{\prime} }| =1$ and, for S = ( s 0 , … , s n − 1 , 0 , … ) ${\mathscr{S}}=({s}_{0},\ldots ,{s}_{n-1},0,\ldots )$ and S ′ = ( s 0 ′ , … , s n − 1 ′ , s n ′ , 0 , … ) ${{\mathscr{S}}}^{^{\prime} }=({s}_{0}^{^{\prime} },\ldots ,{s}_{n-1}^{^{\prime} },{s}_{n}^{^{\prime} },0,\ldots )$ , with edges between ( S , i − 1 , 3 ) $({\mathscr{S}},i-1,3)$ and ( S ′ , 0 , j ′ ) $({{\mathscr{S}}}^{^{\prime} },0,{j}^{^{\prime} })$ and between ( S , i , 3 ) $({\mathscr{S}},i,3)$ and ( S ′ , 0 , j ′ ) $({{\mathscr{S}}}^{^{\prime} },0,{j}^{^{\prime} })$ whenever s n ′ = i ⩾ 1 ${s}_{n}^{^{\prime} }=i\geqslant 1$ and s k = s k ′ ${s}_{k}={s}_{k}^{^{\prime} }$ for all k < n $k\lt n$ . Intuitively, a sequence such as S = ( 3 , 2 , 3 , 0 , 0 , … ) ${\mathscr{S}}=(3,2,3,0,0,\ldots )$ encodes the specific N × 3 ${\mathbb{N}}\times 3$ grid that one encounters when following along the (blue) ( 0 , 0 , 0 , … ) $(0,0,0,\ldots )$ grid, then turning after 3 steps into the (green) ( 3 , 0 , 0 , … ) $(3,0,0,\ldots )$ grid, then turning after another 2 steps into the (black) ( 3 , 2 , 0 , 0 , … ) $(3,2,0,0,\ldots )$ grid, and finally turning after another 3 steps into the ( 3 , 2 , 3 , 0 , 0 , … ) $(3,2,3,0,0,\ldots )$ grid (not depicted). Note that G $G$ is locally finite and connected.

By Lemma 2.2, every linked, tight, componental rooted tree-decomposition of G $G$ into finite parts displays all the ends of G $G$ and their (combined) degrees. Thus, it suffices to show that G $G$ has no rooted tree-decomposition with upwards disjoint adhesion sets, which displays all its ends and their (combined) degrees. Let ( T , V ) $(T,{\mathscr{V}})$ be a tree-decomposition of G $G$ , which displays all ends of G $G$ and their (combined) degrees. Consider the rays R S , j = { ( S , i , j ) ∣ i ∈ N } ${R}_{{\mathscr{S}},j}=\{({\mathscr{S}},i,j)| i\in {\mathbb{N}}\}$ for all S ∈ c ′ ${\mathscr{S}}\in {c}^{^{\prime} }$ with j ∈ { 1 , 2 , 3 } $j\in \{1,2,3\}$ . Then, for every fixed S ∈ c ′ ${\mathscr{S}}\in {c}^{^{\prime} }$ , the rays R S , 1 , R S , 2 , R S , 3 ${R}_{{\mathscr{S}},1},{R}_{{\mathscr{S}},2},{R}_{{\mathscr{S}},3}$ all belong to the same end ε S ${\varepsilon }_{{\mathscr{S}}}$ of G $G$ ; and these ends ε S ${\varepsilon }_{{\mathscr{S}}}$ are pairwise distinct and have (combined) degree 3. Since ( T , V ) $(T,{\mathscr{V}})$ displays all ends of G $G$ and their (combined) degrees, there exist for each ε S ${\varepsilon }_{{\mathscr{S}}}$ infinitely many edges e $e$ of T $T$ such that V e ${V}_{e}$ has size three and meets every ray R S , j ${R}_{{\mathscr{S}},j}$ ; we fix for each end ε S ${\varepsilon }_{{\mathscr{S}}}$ one such edge e S ${e}_{{\mathscr{S}}}$ . Let v S = ( S , i S , 3 ) ${v}_{{\mathscr{S}}}=({\mathscr{S}},{i}_{{\mathscr{S}}},3)$ be the (unique) vertex in V e S ∩ V ( R S , 3 ) ${V}_{{e}_{{\mathscr{S}}}}\cap V({R}_{{\mathscr{S}},3})$ (see Figure 5).

Set S 0 ≔ ( 0 , 0 , … ) ${{\mathscr{S}}}_{0}:= (0,0,\ldots )$ and S n ≔ ( s 0 , … , s n − 1 , i S n − 1 + 1 , 0 , … ) ${{\mathscr{S}}}_{n}:= ({s}_{0},\ldots ,{s}_{n-1},{i}_{{{\mathscr{S}}}_{n-1}}+1,0,\ldots )$ where S n − 1 = ( s 0 , … , s n − 1 , 0 , … ) ${{\mathscr{S}}}_{n-1}=({s}_{0},\ldots ,{s}_{n-1},0,\ldots )$ . Then, the v S n ${v}_{{{\mathscr{S}}}_{n}}$ define a (unique) end ε $\varepsilon $ of G $G$ , in that every ray that meets all the v S n ${v}_{{{\mathscr{S}}}_{n}}$ belongs to the same end ε $\varepsilon $ . This end has degree 2 as witnessed by the sets S n ≔ { ( S n , i S n , 3 ) , ( S n , i S n + 1 , 3 ) } ${S}_{n}:= \{({{\mathscr{S}}}_{n},{i}_{{{\mathscr{S}}}_{n}},3),({{\mathscr{S}}}_{n},{i}_{{{\mathscr{S}}}_{n}}+1,3)\}$ (see Figure 5).

Now since ( T , V ) $(T,{\mathscr{V}})$ displays the (combined) degree of ε $\varepsilon $ , and because the sets S n ${S}_{n}$ are the only separators witnessing that ε $\varepsilon $ has degree 2, there is an edge e ∈ T $e\in T$ with V e = S n ${V}_{e}={S}_{n}$ for some n ∈ N $n\in {\mathbb{N}}$ . But since every such S n ${S}_{n}$ meets the set V e S n ${V}_{{e}_{{{\mathscr{S}}}_{n}}}$ , the tree-decomposition ( T , V ) $(T,{\mathscr{V}})$ does not have upwards disjoint separators. □ $\square $

This example might explain why Halin never extended his result [10, Satz 10] mentioned above to graphs with more than two ends: His precursor notion to a tree-decomposition, namely, the quasitrees and pseudotrees discussed in [17], required upwards disjoint separators and hence could not possibly capture the types of locally finite graphs described in Example 5.2.

Acknowledgements

Open Access funding enabled and organised by Projekt DEAL.

    Endnotes

  1. 1 We remark that this definition extends the one given in [5, Section 2.2] to a larger class of tree-decompositions which do not necessarily have finite adhesion.
  2. 2 The set-theoretic liminf n ∈ ℕ   A n ${\text{liminf}}_{n\in {\rm{{\mathbb{N}}}}}\unicode{x0200A}{A}_{n}$ consists of all points that are contained in all but finitely many A n ${A}_{n}$ . For a ray R = v 0 e 0 v 1 e 1 v 1 … $R={v}_{0}{e}_{0}{v}_{1}{e}_{1}{v}_{1}\ldots $ in T $T$ , one gets liminf e ∈ E ( R ε )   V e = ∪ n ∈ ℕ ∩ i ⩾ n V e i ${\text{liminf}}_{e\in E({R}_{\varepsilon })}\unicode{x0200A}{V}_{e}={\cup }_{n\in {\rm{{\mathbb{N}}}}}{\cap }_{i\geqslant n}{V}_{{e}_{i}}$ .
  3. 3 The example is only presented in the arXiv version of [15].
  4. 4 A set X $X$ of vertices of G $G$ is critical if infinitely many components of G − X $G-X$ have neighbourhood X $X$ in G $G$ .
  5. 5 A ray-decomposition is a tree-decomposition whose decomposition tree is a ray.
  6. 6 We restrict to the set c ′ ${c}^{^{\prime} }$ instead of c 00 ( N ) ${c}_{00}({\mathbb{N}})$ to ensure that G $G$ is connected.

    7. Data Availability Statement

    The authors have nothing to report.

      The full text of this article hosted at iucr.org is unavailable due to technical difficulties.