Journal of Graph Theory
Volume 104, Issue 4 pp. 683-696
ARTICLE
Open Access

Universal graphs for the topological minor relation

Thilo Krill, 

Corresponding Author

Thilo Krill

Department of Mathematics, Universität Hamburg, Hamburg, Germany

Correspondence Thilo Krill, Department of Mathematics, Universität Hamburg, Bundesstrasse 55 (Geomatikum), 20146 Hamburg, Germany.

Email: [email protected]

Search for more papers by this author
First published: 06 June 2023
https://doi.org/10.1002/jgt.22994
Citations: 1

Abstract

A subgraph-universal graph/a topological minor-universal graph in a class of graphs G ${\mathscr{G}}$ is a graph in G ${\mathscr{G}}$ which contains every graph in G ${\mathscr{G}}$ as a subgraph/topological minor. We prove that the class P ${\mathscr{P}}$ of all countable planar graphs does not contain a topological minor-universal graph. This answers a question of Diestel and Kühn and strengthens a result of Pach stating that there is no subgraph-universal graph in P ${\mathscr{P}}$ . Furthermore, we characterise for which subdivided stars T $T$ there is a topological minor-universal graph in the class of all countable T $T$ -free graphs.

1 INTRODUCTION

Let R $R$ be either the subgraph relation, the topological minor relation, or the minor relation. We say that a graph Γ ${\rm{\Gamma }}$ is R $R$ -universal in a class of graphs G ${\mathscr{G}}$ if Γ ∈ G ${\rm{\Gamma }}\in {\mathscr{G}}$ and Γ ${\rm{\Gamma }}$ contains every graph G ∈ G $G\in {\mathscr{G}}$ with respect to R $R$ . In this paper, we investigate the existence of topological minor-universal graphs. All graphs here are countable and we do not distinguish between isomorphic graphs.

Ulam asked whether there exists a subgraph-universal planar graph (cf. [11]), which was answered negatively by Pach:

Theorem 1.1. ((Pach [[11]]))There is no subgraph-universal graph in the class of all planar graphs.

There have been different approaches on how to weaken Ulam's question to obtain a positive answer. For example, Huynh, Mohar, Šámal, Thomassen and Wood recently constructed a graph which contains all planar graphs as subgraphs and is not planar itself, but satisfies a number of properties which are also satisfied by planar graphs [8]. For another approach, Diestel and Kühn showed that there is a minor-universal graph in the class of all planar graphs and asked whether the same is true for topological minor-universality [6]. We answer their question negatively, strengthening Theorem 1.1:

Theorem 1.2.There is no topological minor-universal graph in the class of all planar graphs.

Lehner proved Theorem 1.2 independently in [10]. He showed that every graph G $G$ which contains every planar graph as a topological minor contains arbitrarily large finite cliques as topological minors as well as an infinite clique as a minor. This implies Theorem 1.2 as such a graph G $G$ clearly cannot be planar. At the same time, Lehner's result strengthens a recent result by Huynh et al., who showed the same under the stronger premise that G $G$ contains all planar graphs as subgraphs [8].

We generalise Theorem 1.2 in a different direction than Lehner:

Theorem 1.3.Any class of graphs which is defined by excluding finite topological minors of minimum degree at least 3 contains a topological minor-universal graph if and only if it contains a subgraph-universal graph.

As an application, we strengthen several known results on the nonexistence of subgraph-universal graphs. In particular, Theorem 1.2 is a direct consequence of Theorems 1.1 and 1.3 since the countable planar graphs are precisely the countable graphs without K 3 , 3 ${K}_{3,3}$ and K 5 ${K}^{5}$ as topological minors.

In Sections 4 and 5, we look at topological minor-universal graphs with forbidden subdivided stars. For a graph X $X$ , let Forb ( X ) $\text{Forb}(X)$ be the class of all graphs which do not contain X $X$ as a subgraph. To decide for which graphs X $X$ there is an induced subgraph-universal graph or a subgraph-universal graph in Forb ( X ) $\text{Forb}(X)$ is an ongoing quest which has been solved for many but not for all finite connected graphs X $X$ (see, e.g., [1-3, 7]).

The question whether there exists a topological minor-universal graph in Forb ( X ) $\text{Forb}(X)$ will be solved in this paper for all finite connected graphs X $X$ . However, it is only interesting if X $X$ is a subdivided star for the following reasons. First, it is trivial to find a topological minor-universal graph in Forb ( X ) $\text{Forb}(X)$ if X $X$ is not a subdivided star: If X $X$ contains a cycle, say of length k $k$ , then the infinite clique in which every edge is subdivided k $k$ times is topological minor-universal in Forb ( X ) $\text{Forb}(X)$ . Otherwise X $X$ is a tree but not a subdivided star and thus X $X$ contains two vertices of degree at least three. When we denote their distance in X $X$ by k $k$ , the same graph as above is topological minor-universal in Forb ( X ) $\text{Forb}(X)$ .

Second, the existence of a topological minor-universal graph Γ ${\rm{\Gamma }}$ in a class of graphs G ${\mathscr{G}}$ is especially interesting if G ${\mathscr{G}}$ is closed under topological minors because then Γ ${\rm{\Gamma }}$ yields a characterisation for the graphs in G ${\mathscr{G}}$ : Any graph G $G$ is contained in G ${\mathscr{G}}$ if and only if G $G$ is a topological minor of Γ ${\rm{\Gamma }}$ . Finally, note that Forb ( X ) $\text{Forb}(X)$ is indeed closed under topological minors for any subdivided star X $X$ (in fact, excluding a subdivided star as a subgraph or as a topological minor results in the same). On the other hand, Forb ( X ) $\text{Forb}(X)$ is not closed under topological minors for any other finite connected graphs X $X$ since the universal graph in Forb ( X ) $\text{Forb}(X)$ which we found above contains X $X$ as a topological minor but X ∉ Forb ( X ) $X\notin \text{Forb}(X)$ .

We characterise the existence of topological minor-universal graphs with forbidden subdivided stars as follows:

Theorem 1.4.Let T $T$ be a finite subdivided star. There is a topological minor-universal graph in Forb ( T ) $\text{Forb}(T)$ if and only if at most two of the original edges of T $T$ are subdivided.

A comparison to the following result by Cherlin and Shelah shows that there are fewer positive results if we look at induced subgraph- or subgraph-universal graphs, in particular the condition on the minimum degree in Theorem 1.3 cannot be omitted:

Theorem 1.5. ((Cherlin and Shelah [[1]]))Let T $T$ be a finite tree. There is an induced subgraph-universal graph in Forb ( T ) $\text{Forb}(T)$ if and only if there is a subgraph-universal graph in Forb ( T ) $\text{Forb}(T)$ if and only if T $T$ is either a path or consists of a path with an adjoined edge.

For further research on topological minor-universal graphs, we suggest the following question:

Question 1.6.For which finite connected graphs X $X$ is there a topological minor-universal graph in the class of all graphs without X $X$ as a topological minor?

Both Theorems 1.3 and 1.4 provide a partial answer.

2 PRELIMINARIES

We repeat that all graphs in this paper are countable but from now on we do distinguish between isomorphic graphs. Let G $G$ and H $H$ be graphs. An embedding of G $G$ in H $H$ is an injective map γ : V ( G ) → V ( H ) $\gamma :V(G)\to V(H)$ that preserves adjacency. A topological embedding of G $G$ in H $H$ is an injective map γ : V ( G ) → V ( H ) $\gamma :V(G)\to V(H)$ such that for every edge v w ∈ E ( G ) $vw\in E(G)$ there exists a γ ( v ) $\gamma (v)$ – γ ( w ) $\gamma (w)$ path P v w ${P}^{vw}$ in H $H$ with the following property: For all e ∈ E ( G ) $e\in E(G)$ , the path P e ${P}^{e}$ has no inner vertices in the image of γ $\gamma $ or in any other path P f ${P}^{f}$ with e ≠ f ∈ E ( G ) $e\ne f\in E(G)$ . If there exists an embedding of G $G$ in H $H$ , we write G ≤ H $G\le H$ and if there exists a topological embedding of G $G$ in H $H$ , we write G ⊴ H $G\,\unicode{x022B4}\,H$ . If γ : v ↦ v $\gamma :v\mapsto v$ is an embedding of G $G$ in H $H$ (i.e., if G $G$ is a subgraph of H $H$ ), we write G ⊆ H $G\subseteq H$ . We have G ≤ H $G\le H$ if and only if H $H$ contains a subgraph isomorphic to G $G$ and G ⊴ H $G\,\unicode{x022B4}\,H$ if and only there is a subdivision of G $G$ which is isomorphic to a subgraph of H $H$ . The graph H $H$ is a model of G $G$ if there is a partition { V z : z ∈ V ( G ) } $\{{V}_{z}:z\in V(G)\}$ of V ( H ) $V(H)$ into nonempty connected sets such that for all y ≠ z ∈ V ( G ) $y\ne z\in V(G)$ there is a V y ${V}_{y}$ – V z ${V}_{z}$ edge in H $H$ if and only if y z ∈ E ( G ) $yz\in E(G)$ . We call the sets V z ${V}_{z}$ branch sets. We say that G $G$ is a minor of H $H$ and write G ≼ H $G\,\preccurlyeq \,H$ if H $H$ has a subgraph which is a model of G $G$ .

Let G ${\mathscr{G}}$ be a class of graphs and ⊑ $ \sqsubseteq $ a graph relation, for example, ⊑ ∈ { ≤ , ⊴ , ≼ } $ \sqsubseteq \in \{\le ,\,\unicode{x022B4},\preccurlyeq \}$ . We say that a graph Γ ${\rm{\Gamma }}$ is ⊑ $ \sqsubseteq $ -universal in G ${\mathscr{G}}$ if Γ ∈ G ${\rm{\Gamma }}\in {\mathscr{G}}$ and G ⊑ Γ $G \sqsubseteq {\rm{\Gamma }}$ for all G ∈ G $G\in {\mathscr{G}}$ . We denote by Forb ( G ; ⊑ ) $\text{Forb}({\mathscr{G}}; \sqsubseteq )$ the class of all graphs H $H$ such that there is no graph G ∈ G $G\in {\mathscr{G}}$ with G ⊑ H $G \sqsubseteq H$ . If G = { G 1 , … , G n } ${\mathscr{G}}=\{{G}_{1},\ldots ,{G}_{n}\}$ is finite, we also write Forb ( G 1 , … , G n ; ⊑ ) $\text{Forb}({G}_{1},\ldots ,{G}_{n}; \sqsubseteq )$ for Forb ( G ; ⊑ ) $\text{Forb}({\mathscr{G}}; \sqsubseteq )$ . The graphs in Forb ( G ; ≤ ) $\text{Forb}({\mathscr{G}};\le )$ will be called G ${\mathscr{G}}$ -free.

Let G $G$ be a graph and v ∈ V ( G ) $v\in V(G)$ . We write S G ( v ) ${S}_{G}(v)$ for the subgraph of G $G$ with vertex set { v } ∪ N G ( v ) $\{v\}\cup {N}_{G}(v)$ which contains precisely all edges between v $v$ and its neighbours. We write P n ${P}_{n}$ for a fixed path of length n $n$ and C n ${C}_{n}$ for a fixed cycle of length n $n$ . Next, let P $P$ be a nontrivial path in G $G$ and X $X$ a subset of V ( G ) $V(G)$ . We say that P $P$ is an X $X$ -path if X $X$ contains both endvertices of P $P$ but no inner vertices of P $P$ .

An α $\alpha $ -colouring of a graph G $G$ is a map c : V ( G ) → α $c:V(G)\to \alpha $ , where α $\alpha $ is an ordinal (we will always have either α = 2 $\alpha =2$ or α = ω $\alpha =\omega $ ). We will not explicitly mention the map c $c$ and refer to c ( v ) $c(v)$ as the colour of v $v$ in G $G$ . If we consider a graph G $G$ together with an α $\alpha $ -colouring of G $G$ , we say that G $G$ is an α $\alpha $ -graph. Let G $G$ and H $H$ be α $\alpha $ -graphs. A (topological) α $\alpha $ -embedding of G $G$ in H $H$ is a (topological) embedding of G $G$ in H $H$ which additionally preserves the colour of vertices. We write G ≤ α H $G\,{\le }_{\alpha }H$ if there is an α $\alpha $ -embedding of G $G$ in H $H$ and G ⊴ α H $G\,{\unicode{x022B4}}_{\alpha }\,H$ if there is a topological α $\alpha $ -embedding of G $G$ in H $H$ . We will also use the notions Forb ( X ; ⊑ ) $\text{Forb}({\mathscr{X}}; \sqsubseteq )$ and ⊑ $ \sqsubseteq $ -universality for ⊑ ∈ { ≤ α , ⊴ α } $ \sqsubseteq \in \{{\le }_{\alpha },{\unicode{x022B4}}_{\alpha }\}$ ; all graphs that are involved in their definitions have to be α $\alpha $ -graphs.

3 FORBIDDEN TOPOLOGICAL MINORS AND FORBIDDEN MINORS

Theorem 3.1.If X ${\mathscr{X}}$ is a class of finite graphs with minimum degree at least 3, then G ≔ Forb ( X ; ⊴ ) ${\mathscr{G}}:= \text{Forb}({\mathscr{X}};\unicode{x022B4})$ contains a ⊴ $\unicode{x022B4}$ -universal graph if and only if G ${\mathscr{G}}$ contains a ≤ $\le $ -universal graph.

Proof.Clearly, a ≤ $\le $ -universal graph in G ${\mathscr{G}}$ is also ⊴ $\unicode{x022B4}$ -universal. Conversely, suppose that there is a ⊴ $\unicode{x022B4}$ -universal graph Γ ${\rm{\Gamma }}$ in G ${\mathscr{G}}$ . We construct a ≤ $\le $ -universal graph Γ * ${{\rm{\Gamma }}}^{* }$ in G ${\mathscr{G}}$ as follows. Let V ( Γ * ) ≔ V ( Γ ) $V({{\rm{\Gamma }}}^{* }):= V({\rm{\Gamma }})$ and

E ( Γ * ) ≔ { v w : there are infinitely many independent v - w paths in Γ } . $E({{\rm{\Gamma }}}^{* }):= \{vw:\,\text{there are infinitely many independent}\,\,v \mbox{-} w\,\,\text{paths in}\,\,{\rm{\Gamma }}\}.$

We need to show that Γ * ∈ G ${{\rm{\Gamma }}}^{* }\in {\mathscr{G}}$ and that G ≤ Γ * $G\le {{\rm{\Gamma }}}^{* }$ for every graph G ∈ G $G\in {\mathscr{G}}$ .

First, suppose that Γ * ${{\rm{\Gamma }}}^{* }$ is not a member of G ${\mathscr{G}}$ and thus there is a graph X ∈ X $X\in {\mathscr{X}}$ and a topological embedding γ $\gamma $ of X $X$ in Γ * ${{\rm{\Gamma }}}^{* }$ . Then γ $\gamma $ is also a topological embedding of X $X$ in Γ ${\rm{\Gamma }}$ , contradicting that Γ ∈ G ${\rm{\Gamma }}\in {\mathscr{G}}$ : We recursively find for every edge v w ∈ E ( X ) $vw\in E(X)$ a γ ( v ) $\gamma (v)$ – γ ( w ) $\gamma (w)$ path P v w ${P}^{vw}$ in Γ ${\rm{\Gamma }}$ whose inner vertices avoid V ( X ) $V(X)$ and all paths found in earlier steps. This can be done because there are infinitely many independent γ ( v ) $\gamma (v)$ – γ ( w ) $\gamma (w)$ paths in Γ ${\rm{\Gamma }}$ and the inner vertices of P v w ${P}^{vw}$ only need to avoid finitely many vertices.

Next, we prove that G ≤ Γ * $G\le {{\rm{\Gamma }}}^{* }$ for every graph G ∈ G $G\in {\mathscr{G}}$ . Let G ′ $G^{\prime} $ be the graph obtained from G $G$ by replacing every edge e $e$ with infinitely many independent paths of length 2, whose inner vertices we call v 0 e , v 1 e , v 2 e , … ${v}_{0}^{e},{v}_{1}^{e},{v}_{2}^{e},\ldots $ . We start by showing that G ′ ∈ G $G^{\prime} \in {\mathscr{G}}$ . Suppose that G ′ $G^{\prime} $ has a subgraph that is isomorphic to a subdivision X ′ $X^{\prime} $ of a graph X ∈ X $X\in {\mathscr{X}}$ , without loss of generality we assume that X ′ ⊆ G ′ $X^{\prime} \subseteq G^{\prime} $ . By suppressing every vertex of the form v i e ${v}_{i}^{e}$ in X ′ $X^{\prime} $ (reobtaining the edge e $e$ ), we obtain the graph X ″ ⊆ G $X^{\prime\prime} \subseteq G$ . Also X ″ $X^{\prime\prime} $ is a subdivision of X $X$ , since the minimum degree of X $X$ is at least 3 and hence we only suppressed subdividing vertices. This contradicts G ∈ G $G\in {\mathscr{G}}$ and thus we have G ′ ∈ G $G^{\prime} \in {\mathscr{G}}$ .

Since Γ ${\rm{\Gamma }}$ is ⊴ $\unicode{x022B4}$ -universal in G ${\mathscr{G}}$ , there is a topological embedding γ $\gamma $ of G ′ $G^{\prime} $ in Γ ${\rm{\Gamma }}$ . Then γ ∣ V ( G ) $\gamma {| }_{V(G)}$ is an embedding of G $G$ in Γ * ${{\rm{\Gamma }}}^{* }$ . Indeed, for any edge v w ∈ G $vw\in G$ there are infinitely many independent v $v$ – w $w$ paths in G ′ $G^{\prime} $ . Therefore, there are infinitely many independent γ ( v ) $\gamma (v)$ – γ ( w ) $\gamma (w)$ paths in Γ ${\rm{\Gamma }}$ and thus γ ( v ) γ ( w ) ∈ E ( Γ * ) $\gamma (v)\gamma (w)\in E({{\rm{\Gamma }}}^{* })$ . □ $\square $

The statement of Theorem 3.1 remains true when we exclude minors instead of topological minors:

Corollary 3.2.If X ${\mathscr{X}}$ is a class of finite graphs with minimum degree at least 3, then Forb ( X ; ≼ ) $\text{Forb}({\mathscr{X}};\preccurlyeq )$ contains a ⊴ $\unicode{x022B4}$ -universal graph if and only if it contains a ≤ $\le $ -universal graph.

Proof.Let Y ${\mathscr{Y}}$ be the class of all models of graphs in X ${\mathscr{X}}$ that are finite and have minimum degree at least 3. We will show that Forb ( X ; ≼ ) = Forb ( Y ; ⊴ ) $\text{Forb}({\mathscr{X}};\preccurlyeq )=\text{Forb}({\mathscr{Y}};\unicode{x022B4})$ , then the claim follows from Theorem 3.1. Forb ( X ; ≼ ) ⊆ Forb ( Y ; ⊴ ) $\text{Forb}({\mathscr{X}};\preccurlyeq )\subseteq \text{Forb}({\mathscr{Y}};\unicode{x022B4})$ is clear. For the proof of the converse inclusion, let G $G$ be a graph that is not in Forb ( X ; ≼ ) $\text{Forb}({\mathscr{X}};\preccurlyeq )$ . Thus there is a subgraph X ′ $X^{\prime} $ of G $G$ which is a model of some X ∈ X $X\in {\mathscr{X}}$ . We choose X ′ $X^{\prime} $ so that it has no vertices of degree 1, the branch sets induce finite trees in X ′ $X^{\prime} $ , and there is at most one edge connecting two distinct branch sets. By suppressing all vertices of degree 2 in X ′ $X^{\prime} $ , we obtain a topological minor Y $Y$ of X ′ $X^{\prime} $ with minimum degree at least 3. Since also the minimum degree of X $X$ is at least 3, every branch set in X ′ $X^{\prime} $ contains a vertex of degree at least 3 which was not suppressed in the construction of Y $Y$ . Therefore, X $X$ is a minor of Y $Y$ . Additionally, Y $Y$ contains no loops or double edges because every cycle in X ′ $X^{\prime} $ contains at least three vertices of degree at least 3 in X ′ $X^{\prime} $ , one for each branch set it traverses. Thus, Y ∈ Y $Y\in {\mathscr{Y}}$ . Since Y ⊴ X ′ ⊆ G $Y\,\unicode{x022B4}\,X^{\prime} \subseteq G$ , it follows that G $G$ is not contained in Forb ( Y ; ⊴ ) $\text{Forb}({\mathscr{Y}};\unicode{x022B4})$ . □ $\square $

Corollary 3.3.The following classes of graphs do not contain ⊴ $\unicode{x022B4}$ -universal graphs:

  • (1)

    Forb ( K 5 , K 3 , 3 ; ⊴ ) $\text{Forb}({K}^{5},{K}_{3,3};\unicode{x022B4})$ (the planar graphs),

  • (2)

    Forb ( K n ; ⊴ ) $\text{Forb}({K}^{n};\unicode{x022B4})$ for n ≥ 5 $n\ge 5$ ,

  • (3)

    Forb ( K n , m ; ⊴ ) $\text{Forb}({K}_{n,m};\unicode{x022B4})$ for n , m ≥ 3 $n,m\ge 3$ ,

  • (4)

    Forb ( K n ; ≼ ) $\text{Forb}({K}^{n};\preccurlyeq )$ for n ≥ 5 $n\ge 5$ .

Proof.The claim follows from Theorem 3.1, Corollary 3.2 and the fact that none of these classes contains a ≤ $\le $ -universal graph: Pach [11] showed that there is no ≤ $\le $ -universal planar graph, Diestel, Halin and Vogler [5] showed the same for the classes in (2) and (4) and Diestel [4] for the classes in (3). □ $\square $

4 FORBIDDEN SUBDIVIDED STARS—POSITIVE RESULTS

In this section we prove Theorem 4.2, which states that there is a ⊴ $\unicode{x022B4}$ -universal T $T$ -free graph if T $T$ is a subdivided star in which at most 2 of the original edges are subdivided. We use the following notation for subdivided stars:

Definition 4.1.Let k ∈ N $k\in {\mathbb{N}}$ and p 1 ≤ ⋯ ≤ p k ∈ ℕ ${p}_{1}\le \,\cdots \,\le {p}_{k}\in {\rm{{\mathbb{N}}}}$ and let P 1 , … , P k ${P}^{1},\ldots ,{P}^{k}$ be disjoint paths such that the length of P i ${P}^{i}$ is p i ${p}_{i}$ for all i ≤ k $i\le k$ .

We write T ( p 1 , … , p k ) $T({p}_{1},\ldots ,{p}_{k})$ for the graph obtained from the paths P 1 , … , P k ${P}^{1},\ldots ,{P}^{k}$ by adding a vertex c $c$ and identifying one endvertex of each path P i ${P}^{i}$ with c $c$ . We call c $c$ the centre of T ( p 1 , … , p k ) $T({p}_{1},\ldots ,{p}_{k})$ . If p 1 = ⋯ = p k = 1 ${p}_{1}=\,\cdots \,={p}_{k}=1$ , then we also write S k ${S}_{k}$ for T ( p 1 , … , p k ) $T({p}_{1},\ldots ,{p}_{k})$ .

Theorem 4.2.Let k ∈ N $k\in {\mathbb{N}}$ and p 1 ≤ ⋯ ≤ p k ∈ ℕ ${p}_{1}\le \cdots \,\le {p}_{k}\in {\rm{{\mathbb{N}}}}$ . If k ≤ 2 $k\le 2$ or if k ≥ 3 $k\ge 3$ and p k − 2 = 1 ${p}_{k-2}=1$ , then there exists a ⊴ $\unicode{x022B4}$ -universal graph in Forb ( T ( p 1 , … , p k ) ; ≤ ) $\text{Forb}(T({p}_{1},\ldots ,{p}_{k});\le )$ .

For the rest of this section, we write T $T$ for the graph T ( p 1 , … , p k ) $T({p}_{1},\ldots ,{p}_{k})$ from Theorem 4.2. For paths T $T$ , Komjáth, Mekler and Pach [9] showed that there exists a ≤ $\le $ -universal graph in Forb ( T ; ≤ ) $\text{Forb}(T;\le )$ , which is also ⊴ $\unicode{x022B4}$ -universal. In the following, we will therefore assume that k ≥ 3 $k\ge 3$ and p k − 2 = 1 ${p}_{k-2}=1$ .

We begin by proving the existence of a ⊴ $\unicode{x022B4}$ -universal S k ${S}_{k}$ -free graph or, equivalently, a ⊴ $\unicode{x022B4}$ -universal graph of maximum degree k − 1 $k-1$ . (In Lemma 4.3, we prove that there is a ⊴ $\unicode{x022B4}$ -universal connected S k ${S}_{k}$ -free graph. By taking countably many disjoint copies of that universal graph, we obtain a ⊴ $\unicode{x022B4}$ -universal graph for all S k ${S}_{k}$ -free graphs that are not necessarily connected.)

Lemma 4.3.There is a ⊴ ω ${\unicode{x022B4}}_{\omega }$ -universal ω $\omega $ -graph Γ * ${{\rm{\Gamma }}}^{* }$ in the class G ${\mathscr{G}}$ of all connected S k ${S}_{k}$ -free ω $\omega $ -graphs on at least three vertices, such that Γ * ${{\rm{\Gamma }}}^{* }$ satisfies the following stronger assertion: For every ω $\omega $ -graph G ∈ G $G\in {\mathscr{G}}$ there is a topological ω $\omega $ -embedding γ * ${\gamma }^{* }$ of G $G$ in Γ * ${{\rm{\Gamma }}}^{* }$ which is degree preserving, that is, d G ( v ) = d Γ * ( γ * ( v ) ) ${d}_{G}(v)={d}_{{{\rm{\Gamma }}}^{* }}({\gamma }^{* }(v))$ for all v ∈ V ( G ) $v\in V(G)$ .

Proof.Let [ N ] < k ${[{\mathbb{N}}]}^{\lt k}$ be the (countable) set of all subsets of N ${\mathbb{N}}$ of size less than k $k$ and choose a function f : N ≥ 1 → [ N ] < k $f:{{\mathbb{N}}}_{\ge 1}\to {[{\mathbb{N}}]}^{\lt k}$ such that for every A ∈ [ N ] < k $A\in {[{\mathbb{N}}]}^{\lt k}$ there are infinitely many n ∈ N ≥ 1 $n\in {{\mathbb{N}}}_{\ge 1}$ with f ( n ) = A $f(n)=A$ . Furthermore, let ( R i : i ∈ N ) $({R}_{i}:i\in {\mathbb{N}})$ be a family of pairwise disjoint rays. Now we construct Γ * ${{\rm{\Gamma }}}^{* }$ from the graph ⋃ i ∈ N R i ${\bigcup }_{i\in {\mathbb{N}}}{R}_{i}$ by adding for all j ∈ N ≥ 1 $j\in {{\mathbb{N}}}_{\ge 1}$ a vertex v j ${v}_{j}$ , which we join to the j $j$ th vertex of each ray R i ${R}_{i}$ with i ∈ f ( j ) $i\in f(j)$ (see Figure 1). We define an ω $\omega $ -colouring of Γ * ${{\rm{\Gamma }}}^{* }$ in such a way that for every set A ∈ [ N ] < k $A\in {[{\mathbb{N}}]}^{\lt k}$ and for every colour c ∈ N $c\in {\mathbb{N}}$ , there is an integer j ∈ f − 1 ( A ) $j\in {f}^{-1}(A)$ such that v j ${v}_{j}$ has colour c $c$ . This is possible because f − 1 ( A ) ${f}^{-1}(A)$ is infinite for all A ∈ [ N ] < k $A\in {[{\mathbb{N}}]}^{\lt k}$ . The vertices of ⋃ i ∈ N R i ${\bigcup }_{i\in {\mathbb{N}}}{R}_{i}$ may be coloured arbitrarily.

Γ * ${{\rm{\Gamma }}}^{* }$ does not contain a copy of S k ${S}_{k}$ because the vertices v j ${v}_{j}$ for j ∈ N $j\in {\mathbb{N}}$ have degree less than k $k$ and all other vertices have degree at most 3. It remains to find a degree preserving topological ω $\omega $ -embedding γ * ${\gamma }^{* }$ of G $G$ in Γ * ${{\rm{\Gamma }}}^{* }$ for every ω $\omega $ -graph G ∈ G $G\in {\mathscr{G}}$ . We enumerate E ( G ) ≕ { e 0 , e 1 , … } $E(G)=:\,\{{e}_{0},{e}_{1},\ldots \}$ . For every vertex v ∈ V ( G ) $v\in V(G)$ , we pick an integer

j ∈ f − 1 ( { i ∈ N : v is incident to e i in G } ) $j\in {f}^{-1}(\{i\in {\mathbb{N}}:v\,\,\text{is incident to}\,\,{e}_{i}\,\,\text{in}\,\,G\})$
such that v $v$ has the same colour in G $G$ as v j ≕ γ * ( v ) ${v}_{j}=:{\gamma }^{* }(v)$ in Γ ${\rm{\Gamma }}$ . Then clearly, γ * ${\gamma }^{* }$ is degree preserving. Next, γ * ${\gamma }^{* }$ is injective since in a connected graph on at least three vertices, the set of incident edges is different for every vertex. Finally, for all edges e i = v w ∈ E ( G ) ${e}_{i}=vw\in E(G)$ we have to find internally disjoint γ * ( v ) ${\gamma }^{* }(v)$ – γ * ( w ) ${\gamma }^{* }(w)$ paths P e i ${P}^{{e}_{i}}$ in Γ * ${{\rm{\Gamma }}}^{* }$ which avoid the image of γ * ${\gamma }^{* }$ . Each path P e i ${P}^{{e}_{i}}$ can be built using the ray R i ${R}_{i}$ together with the γ * ( v ) ${\gamma }^{* }(v)$ – R i ${R}_{i}$ edge and the γ * ( w ) ${\gamma }^{* }(w)$ – R i ${R}_{i}$ edge in Γ * ${{\rm{\Gamma }}}^{* }$ . □ $\square $

Details are in the caption following the image
Figure 1
Open in figure viewerPowerPoint
The graph Γ * ${{\rm{\Gamma }}}^{* }$ when f ( 1 ) = { 0 , 1 } , f ( 2 ) = { 0 , 2 } , f ( 3 ) = { 0 , 1 } , … $f(1)=\{0,1\},f(2)=\{0,2\},f(3)=\{0,1\},\ldots $ drawn without regarding its vertex colouring.

We remark that we can also use the construction of Γ ${\rm{\Gamma }}$ in the proof of Lemma 4.3 for building a ⊴ $\unicode{x022B4}$ -universal graph in the class of all locally finite graphs if we replace [ N ] < k ${[{\mathbb{N}}]}^{\lt k}$ by [ N ] < ω ${[{\mathbb{N}}]}^{\lt \omega }$ . A ≤ $\le $ -universal locally finite graph however does not exist; this is an easy observation which was first made by de Brujn, see [12].

Our next aim in the proof of Theorem 4.2 is Lemma 4.6, a result on the structure of T $T$ -free graphs. In the proof of Lemma 4.6, we analyse the block structure of T $T$ -free graphs (a block of a graph G $G$ is a maximal connected subgraph of G $G$ without a cutvertex). We need the following lemmas:

Lemma 4.4. ((Diestel [[4], Chap. 1, Exercise 3]))Let n ∈ N $n\in {\mathbb{N}}$ . Every 2-connected graph G $G$ containing a path of length n 2 ${n}^{2}$ contains a cycle of length at least n $n$ .

We recall that k ≥ 3 , p k − 2 = 1 $k\ge 3,{p}_{k-2}=1$ and T = T ( p 1 , … , p k ) $T=T({p}_{1},\ldots ,{p}_{k})$ .

Lemma 4.5.Let G $G$ be a T $T$ -free graph and let B $B$ be a block of G $G$ that contains a vertex v ∈ V ( B ) $v\in V(B)$ with d G ( v ) ≥ k ${d}_{G}(v)\ge k$ . Then there is no path of length m ≔ ( k + 1 ) 2 ( 2 p k ) 2 $m:= {(k+1)}^{2}{(2{p}_{k})}^{2}$ in B $B$ .

Proof.Suppose for a contradiction that B $B$ contains a path of length m $m$ . Therefore, ∣ B ∣ ≥ 3 $| B| \ge 3$ and it follows that B $B$ is 2-connected. By Lemma 4.4, there is a cycle C $C$ in B $B$ of length at least m = ( k + 1 ) ⋅ 2 p k $\sqrt{m}=(k+1)\cdot 2{p}_{k}$ . First we consider the case that S B ( v ) ∩ C = ∅ ${S}_{B}(v)\cap C=\varnothing $ . By 2-connectedness of B $B$ there are two disjoint S B ( v ) ${S}_{B}(v)$ – C $C$ paths P 1 ${P}^{1}$ and P 2 ${P}^{2}$ in B $B$ . Denote the endvertex of P i ${P}^{i}$ in C $C$ by x i ${x}_{i}$ . We can find an x 1 ${x}_{1}$ – x 2 ${x}_{2}$ path Q $Q$ in C $C$ of length at least 2 p k + 1 $2{p}_{k}+1$ since ∣ C ∣ ≥ 8 p ≥ 2 ( 2 p k + 1 ) $| C| \ge 8p\ge 2(2{p}_{k}+1)$ . However, there is a copy of T $T$ in S G ( v ) ∪ P 1 ∪ P 2 ∪ Q ${S}_{G}(v)\cup {P}^{1}\cup {P}^{2}\cup Q$ , a contradiction.

If S B ( v ) ∩ C = { w } ${S}_{B}(v)\cap C=\{w\}$ for some vertex w $w$ , then let P 1 = w ${P}^{1}=w$ be a path of length 1. Note that w ≠ v $w\ne v$ . Since B $B$ is 2-connected, there is an S B ( v ) ${S}_{B}(v)$ – C $C$ path P 2 ${P}^{2}$ in B − w $B-w$ . Now we can prove that T ≤ G $T\le G$ as in the case S B ( v ) ∩ C = ∅ ${S}_{B}(v)\cap C=\varnothing $ .

Finally, suppose that ∣ V ( S B ( v ) ) ∩ V ( C ) ∣ ≥ 2 $| V({S}_{B}(v))\cap V(C)| \ge 2$ . There are at most ∣ S B ( v ) ∣ = k + 1 $| {S}_{B}(v)| =k+1$ many distinct S B ( v ) ${S}_{B}(v)$ -paths contained in C $C$ . Therefore, there must be an S B ( v ) ${S}_{B}(v)$ -path P $P$ in C $C$ of length at least 2 p k $2{p}_{k}$ since ∣ C ∣ ≥ ( k + 1 ) ⋅ 2 p k $| C| \ge (k+1)\cdot 2{p}_{k}$ . This is a contradiction as S G ( v ) ∪ P ${S}_{G}(v)\cup P$ contains a copy of T $T$ . □ $\square $

Lemma 4.6.Let m $m$ be as in Lemma 4.5 and let G $G$ be a connected T $T$ -free graph with P 4 p k m ≤ G ${P}_{4{p}_{k}m}\le G$ . Then there is a connected induced subgraph G * ${G}^{* }$ of G $G$ and for every vertex v ∈ V ( G * ) $v\in V({G}^{* })$ there is a connected induced subgraph G v ${G}_{v}$ of G $G$ such that the following properties hold:

  • (1)

    G = G * ∪ ⋃ v ∈ V ( G * ) G v $G={G}^{* }\cup {\bigcup }_{v\in V({G}^{* })}{G}_{v}$ ,

  • (2)

    G * ∩ G v = { v } ${G}^{* }\cap {G}_{v}=\{v\}$ and G v ∩ G w = ∅ ${G}_{v}\cap {G}_{w}=\varnothing $ for all v ≠ w ∈ V ( G * ) $v\ne w\in V({G}^{* })$ ,

  • (3)

    d G ( v ) < k ${d}_{G}(v)\lt k$ for all v ∈ V ( G * ) $v\in V({G}^{* })$ ,

  • (4)

    P 2 p k ≤ G * ${P}_{2{p}_{k}}\le {G}^{* }$ and

  • (5)

    P 8 p k + 2 m ≰ G v ${P}_{8{p}_{k}+2m}\,\nleqq \,{G}_{v}$ for all v ∈ V ( G * ) $v\in V({G}^{* })$ .

Proof.Let A $A$ be the set of cutvertices in G $G$ and B ${\rm{ {\mathcal B} }}$ the set of blocks of G $G$ and K $K$ the block graph of G $G$ . Recall that V ( K ) = A ∪ B $V(K)=A\cup {\rm{ {\mathcal B} }}$ and E ( G ) = { a B : a ∈ A , B ∈ B , a ∈ B } $E(G)=\{aB:a\in A,B\in {\rm{ {\mathcal B} }},a\in B\}$ and that K $K$ is a tree. Since G $G$ contains a path of length 4 p k m $4{p}_{k}m$ , there is either a block B ∈ B $B\in {\rm{ {\mathcal B} }}$ containing a path of length m $m$ or there is a path P = B 1 a 1 B 2 a 2 … B 4 p k − 1 a 4 p k − 1 B 4 p k $P={B}_{1}{a}_{1}{B}_{2}{a}_{2}\,\ldots \,{B}_{4{p}_{k}-1}{a}_{4{p}_{k}-1}{B}_{4{p}_{k}}$ in K $K$ containing 4 p k $4{p}_{k}$ blocks. In the first case let H * ≔ B ${H}^{* }:= B$ and in the second case let

H * ≔ ⋃ p k + 1 ≤ i ≤ 3 p k B i . ${H}^{* }:= \bigcup _{{p}_{k}+1\le i\le 3{p}_{k}}{B}_{i}.$

In both cases, there is clearly a path of length 2 p k $2{p}_{k}$ in H * ${H}^{* }$ . We also have d G ( v ) < k ${d}_{G}(v)\lt k$ for all v ∈ V ( H * ) $v\in V({H}^{* })$ : In the first case, this holds by Lemma 4.5. For the second case, let us suppose that there are a block B i ${B}_{i}$ with p k + 1 ≤ i ≤ 3 p k ${p}_{k}+1\le i\le 3{p}_{k}$ and a vertex v ∈ B i $v\in {B}_{i}$ with d G ( v ) ≥ k ${d}_{G}(v)\ge k$ . Since B i ${B}_{i}$ is 2-connected, there is an S B i ( v ) ${S}_{{B}_{i}}(v)$ – a i − 1 ${a}_{i-1}$ path P 1 ${P}^{1}$ and an S B i ( v ) ${S}_{{B}_{i}}(v)$ – a i ${a}_{i}$ path P 2 ${P}^{2}$ in B i ${B}_{i}$ such that P 1 ${P}^{1}$ and P 2 ${P}^{2}$ are disjoint. Now we extend S G ( v ) ∪ P 1 ∪ P 2 ${S}_{G}(v)\cup {P}^{1}\cup {P}^{2}$ to a copy of T $T$ in G $G$ by extending the path P 1 ${P}^{1}$ into the blocks B j ${B}_{j}$ with j < i $j\lt i$ and extending P 2 ${P}^{2}$ into the blocks B j ${B}_{j}$ with j > i $j\gt i$ . This contradicts G $G$ being T $T$ -free. Hence d G ( v ) < k ${d}_{G}(v)\lt k$ for all v ∈ V ( H * ) $v\in V({H}^{* })$ .

If K ′ $K^{\prime} $ is a subtree of K $K$ , we write ⋃ K ′ $\bigcup K^{\prime} $ for ⋃ { B ∈ B : B ∈ V ( K ′ ) } $\bigcup \{B\in {\rm{ {\mathcal B} }}:B\in V(K^{\prime} )\}$ . Let K ̃ * ${\widetilde{K}}^{* }$ be the maximal subtree of K $K$ that contains all vertices of K $K$ which are blocks of H * ${H}^{* }$ , such that there is no vertex v ∈ ⋃ K ̃ * $v\in \bigcup {\widetilde{K}}^{* }$ with d G ( v ) ≥ k ${d}_{G}(v)\ge k$ . We delete all leaves of K ̃ * ${\widetilde{K}}^{* }$ that are cutvertices in G $G$ and call the resulting graph K * ${K}^{* }$ . Then

G * ≔ ⋃ K * ${G}^{* }:= \bigcup {K}^{* }$
satisfies property (3) by definition of K * ${K}^{* }$ and property (4) since already H * ${H}^{* }$ contains a path of length 2 p k $2{p}_{k}$ .

For all components H $H$ of K − K * $K-{K}^{* }$ we have G * ∩ ⋃ H = { v } ${G}^{* }\cap \bigcup H=\{v\}$ for some vertex v ∈ V ( G * ) ∩ A $v\in V({G}^{* })\cap A$ . Let K v ≔ H ${K}_{v}:= H$ and G v ≔ ⋃ K v ${G}_{v}:= \bigcup {K}_{v}$ . For the proof of property (5), we begin by decomposing G v ${G}_{v}$ into a family G v ${{\mathscr{G}}}_{v}$ of graphs that only intersect in v $v$ . Let K v ${{\mathscr{K}}}_{v}$ be the set of components of K v − v ${K}_{v}-v$ and G v ≔ { ⋃ K ′ : K ′ ∈ K v } ${{\mathscr{G}}}_{v}:= \{\bigcup K^{\prime} :K^{\prime} \in {{\mathscr{K}}}_{v}\}$ . For all K ′ ∈ K v $K^{\prime} \in {{\mathscr{K}}}_{v}$ we show that the graph G ′ ≔ ⋃ K ′ ∈ G v $G^{\prime} := \bigcup K^{\prime} \in {{\mathscr{G}}}_{v}$ (Figure 2) is P 4 p k + m ${P}_{4{p}_{k}+m}$ -free, which implies that G v ${G}_{v}$ is P 8 p k + 2 m ${P}_{8{p}_{k}+2m}$ -free and thus proves property (5).

Let D $D$ be the block of G ′ $G^{\prime} $ containing v $v$ . By maximality of K * ${K}^{* }$ , we know that D $D$ contains a vertex w $w$ with d G ( w ) ≥ k ${d}_{G}(w)\ge k$ . Therefore, Lemma 4.5 implies that D $D$ does not contain a path of length m $m$ . Additionally, for every component K ″ $K^{\prime\prime} $ of K ′ − D $K^{\prime} -D$ the graph G ″ ≔ ⋃ K ″ $G^{\prime\prime} := \bigcup K^{\prime\prime} $ does not contain a path of length 2 p k $2{p}_{k}$ (Figure 2): Suppose that G ″ $G^{\prime\prime} $ contains a path P ″ $P^{\prime\prime} $ of length 2 p k $2{p}_{k}$ . We denote the unique vertex in D ∩ G ″ $D\cap G^{\prime\prime} $ by u $u$ . Let P x ${P}_{x}$ be an S D ( w ) ${S}_{D}(w)$ – x $x$ path in D $D$ for x ∈ { v , u } $x\in \{v,u\}$ such that P v ${P}_{v}$ and P u ${P}_{u}$ are disjoint. Further, let P * ${P}^{* }$ be a path of length 2 p k $2{p}_{k}$ in G * ${G}^{* }$ , which exists by property (4), and let Q v ${Q}_{v}$ be a v $v$ – P * ${P}^{* }$ path in G * ${G}^{* }$ and Q u ${Q}_{u}$ a u $u$ – P ″ $P^{\prime\prime} $ path in G ″ $G^{\prime\prime} $ . However,

S G ( w ) ∪ P v ∪ P u ∪ Q v ∪ Q u ∪ P * ∪ P ″ ⊆ G ${S}_{G}(w)\cup {P}_{v}\cup {P}_{u}\cup {Q}_{v}\cup {Q}_{u}\cup {P}^{* }\cup P^{\prime\prime} \subseteq G$
contains a copy of T $T$ . Therefore, G ″ = ⋃ K ″ $G^{\prime\prime} =\bigcup K^{\prime\prime} $ does not contain a path of length 2 p k $2{p}_{k}$ for every choice of K ″ $K^{\prime\prime} $ . Together with D $D$ being P m ${P}_{m}$ -free, this implies that there is no path of length 4 p k + m $4{p}_{k}+m$ in G ′ $G^{\prime} $ .

Finally, for all v ∈ V ( G * ) $v\in V({G}^{* })$ for which G v ${G}_{v}$ has not been defined yet, let G v ≔ { v } ${G}_{v}:= \{v\}$ . Then properties (1) and (2) are clearly satisfied. □ $\square $

Details are in the caption following the image
Figure 2
Open in figure viewerPowerPoint
The graph G $G$ and its subgraphs.

For the proof of Theorem 4.2, we need the following lemma by Cherlin and Tallgren:

Lemma 4.7. ((Cherlin and Tallgren [[3]]))Let α ∈ N $\alpha \in {\mathbb{N}}$ and let X ${\mathscr{X}}$ be a finite set of finite connected α $\alpha $ -graphs. Suppose that for some n ∈ N $n\in {\mathbb{N}}$ , every α $\alpha $ -coloured version of P n ${P}_{n}$ is contained in X ${\mathscr{X}}$ . Then there is a ≤ α ${\le }_{\alpha }$ -universal α $\alpha $ -graph in Forb ( X ; ≤ α ) $\text{Forb}({\mathscr{X}};{\le }_{\alpha })$ .

The idea for our proof of Theorem 4.2 is to build a ⊴ $\unicode{x022B4}$ -universal graph Γ ${\rm{\Gamma }}$ in Forb ( T ; ≤ ) $\text{Forb}(T;\le )$ by starting with the ⊴ $\unicode{x022B4}$ -universal S k ${S}_{k}$ -free graph Γ * ${{\rm{\Gamma }}}^{* }$ from Lemma 4.3 and attaching to every vertex v ∈ V ( Γ * ) $v\in V({{\rm{\Gamma }}}^{* })$ a ≤ $\le $ -universal P 8 p k + 2 m ${P}_{8{p}_{k}+2m}$ -free graph Γ v ${{\rm{\Gamma }}}_{v}$ that exists by Lemma 4.7. If G $G$ is any connected T $T$ -free graph, we want to decompose G $G$ as in Lemma 4.6 and find a topological embedding γ $\gamma $ of G $G$ in Γ ${\rm{\Gamma }}$ by embedding G * ${G}^{* }$ in Γ * ${{\rm{\Gamma }}}^{* }$ and each graph G v ${G}_{v}$ in Γ γ ( v ) ${{\rm{\Gamma }}}_{\gamma (v)}$ .

Proof of Theorem 4.2.Recall that we have already seen that the theorem holds for k = 2 $k=2$ , so we can assume that k ≥ 3 $k\ge 3$ . We will build a graph Γ ${\rm{\Gamma }}$ that is ⊴ $\unicode{x022B4}$ -universal in the class of all connected T $T$ -free graphs containing P 4 p k m ${P}_{4{p}_{k}m}$ . By Lemma 4.7 (applied with α = 1 $\alpha =1$ ), there exists a ≤ $\le $ -universal graph Γ ′ ${\rm{\Gamma }}^{\prime} $ in Forb ( T , P 4 p k m ; ≤ ) $\text{Forb}(T,{P}_{4{p}_{k}m};\le )$ . Then the disjoint union of Γ ′ ${\rm{\Gamma }}^{\prime} $ with countably many copies of Γ ${\rm{\Gamma }}$ is ⊴ $\unicode{x022B4}$ -universal in Forb ( T ; ≤ ) $\text{Forb}(T;\le )$ .

If H $H$ is a 2-graph with exactly one vertex v $v$ of colour 1, then we write H ¯ $\bar{H}$ for the graph obtained from H $H$ by attaching a path of length p k ${p}_{k}$ to v $v$ . Let

  • X 1 ${{\mathscr{X}}}_{1}$ be the set of all connected 2-graphs H $H$ with V ( H ) ⊆ { 1 , … , ∣ T ∣ } $V(H)\subseteq \{1,\ldots ,| T| \}$ such that H $H$ contains exactly one vertex of colour 1 and T ≤ H ¯ $T\le \bar{H}$ ,

  • X 2 ${{\mathscr{X}}}_{2}$ be the set of all 2-coloured versions of the graph P 8 p k + 2 m ${P}_{8{p}_{k}+2m}$ and

  • X 3 ${{\mathscr{X}}}_{3}$ be the set of all 2-coloured versions P $P$ of the paths P i ${P}_{i}$ for i < 8 p k + 2 m $i\lt 8{p}_{k}+2m$ such that all the inner vertices of P $P$ have colour 0 and the endvertices have colour 1.

For all n < k $n\lt k$ , let

  • X 4 n ${{\mathscr{X}}}_{4}^{n}$ be the one-element set containing the 2-graph S n + 1 ${S}_{n+1}$ so that the centre of S n + 1 ${S}_{n+1}$ has colour 1 and all other vertices have colour 0 and

  • X n ≔ X 1 ∪ X 2 ∪ X 3 ∪ X 4 n ${{\mathscr{X}}}^{n}:= {{\mathscr{X}}}_{1}\cup {{\mathscr{X}}}_{2}\cup {{\mathscr{X}}}_{3}\cup {{\mathscr{X}}}_{4}^{n}$ .

Since X 2 ⊆ X n ${{\mathscr{X}}}_{2}\subseteq {{\mathscr{X}}}^{n}$ , there exists a ≤ 2 ${\le }_{2}$ -universal X n ${{\mathscr{X}}}^{n}$ -free 2-graph Γ n ${{\rm{\Gamma }}}^{n}$ by Lemma 4.7. We fix an enumeration Γ 0 n , Γ 1 n , Γ 2 n … ${{\rm{\Gamma }}}_{0}^{n},{{\rm{\Gamma }}}_{1}^{n},{{\rm{\Gamma }}}_{2}^{n}\,\ldots $ of all components of Γ n ${{\rm{\Gamma }}}^{n}$ which contain a vertex of degree at least n $n$ that has colour 1. Note that each component Γ i n ${{\rm{\Gamma }}}_{i}^{n}$ contains exactly one vertex u $u$ of colour 1 because Γ i n ${{\rm{\Gamma }}}_{i}^{n}$ is connected and X 2 ∪ X 3 ${{\mathscr{X}}}_{2}\cup {{\mathscr{X}}}_{3}$ -free. The degree of u $u$ must be n $n$ since Γ i n ${{\rm{\Gamma }}}_{i}^{n}$ is X 4 n ${{\mathscr{X}}}_{4}^{n}$ -free.

Let Γ * ${{\rm{\Gamma }}}^{* }$ be the ω $\omega $ -graph from Lemma 4.3. For every vertex v ∈ V ( Γ * ) $v\in V({{\rm{\Gamma }}}^{* })$ , let Γ v ≔ Γ c ( v ) n ( v ) ${{\rm{\Gamma }}}_{v}:= {{\rm{\Gamma }}}_{c(v)}^{n(v)}$ where

n ( v ) ≔ k − d Γ * ( v ) − 1 $n(v):= k-{d}_{{{\rm{\Gamma }}}^{* }}(v)-1$
and c ( v ) $c(v)$ is the colour of v $v$ in Γ * ${{\rm{\Gamma }}}^{* }$ . Notice that n ( v ) ≥ 0 $n(v)\ge 0$ since Γ * ${{\rm{\Gamma }}}^{* }$ is S k ${S}_{k}$ -free. By renaming vertices of each Γ v ${{\rm{\Gamma }}}_{v}$ , we obtain for all v ≠ w ∈ V ( Γ * ) $v\ne w\in V({{\rm{\Gamma }}}^{* })$ that Γ v ${{\rm{\Gamma }}}_{v}$ and Γ w ${{\rm{\Gamma }}}_{w}$ are disjoint, the unique vertex of colour 1 in Γ v ${{\rm{\Gamma }}}_{v}$ is v $v$ , and Γ * ∩ Γ v = { v } ${{\rm{\Gamma }}}^{* }\cap {{\rm{\Gamma }}}_{v}=\{v\}$ . We define (the uncoloured graph)
Γ ≔ Γ * ∪ ⋃ v ∈ V ( Γ * ) Γ v . ${\rm{\Gamma }}:= {{\rm{\Gamma }}}^{* }\cup \bigcup _{v\in V({{\rm{\Gamma }}}^{* })}{{\rm{\Gamma }}}_{v}.$

We need to show that Γ ${\rm{\Gamma }}$ is T $T$ -free and that G ⊴ Γ $G\,\unicode{x022B4}\,{\rm{\Gamma }}$ for every connected T $T$ -free graph G $G$ with P 4 p k m ≤ G ${P}_{4{p}_{k}m}\le G$ .

Suppose for a contradiction that there is an embedding γ $\gamma $ of T $T$ in Γ ${\rm{\Gamma }}$ and let z $z$ be the centre of T $T$ . We have γ ( z ) ∈ Γ v − Γ * $\gamma (z)\in {{\rm{\Gamma }}}_{v}-{{\rm{\Gamma }}}^{* }$ for some v ∈ V ( Γ * ) $v\in V({{\rm{\Gamma }}}^{* })$ since any vertex u ∈ V ( Γ * ) $u\in V({{\rm{\Gamma }}}^{* })$ satisfies d Γ ( u ) = d Γ * ( u ) + d Γ u ( u ) = k − 1 ${d}_{{\rm{\Gamma }}}(u)={d}_{{{\rm{\Gamma }}}^{* }}(u)+{d}_{{{\rm{\Gamma }}}_{u}}(u)=k-1$ . Therefore, γ ( T ) ∩ Γ * $\gamma (T)\cap {{\rm{\Gamma }}}^{* }$ is either empty or a path of length at most p k ${p}_{k}$ with endvertex v $v$ , which contradicts Γ v ${{\rm{\Gamma }}}_{v}$ being X 1 ${{\mathscr{X}}}_{1}$ -free.

Now let G $G$ be an arbitrary connected T $T$ -free graph with P 4 p k m ≤ G ${P}_{4{p}_{k}m}\le G$ and consider the graph G * ${G}^{* }$ and the graphs G v ${G}_{v}$ from Lemma 4.6. We furnish each G v ${G}_{v}$ with a 2-colouring by colouring v $v$ with 1 and all other vertices with 0. Then G v ${G}_{v}$ is X 1 ${{\mathscr{X}}}_{1}$ -free: Suppose that there is a graph H ∈ X 1 $H\in {{\mathscr{X}}}_{1}$ and a 2-embedding f $f$ from H $H$ to G v ${G}_{v}$ . Since G * ${G}^{* }$ is connected with P 2 p k ≤ G * ${P}_{2{p}_{k}}\le {G}^{* }$ by Lemma 4.6(4), there is a path P $P$ of length p k ${p}_{k}$ in G * ${G}^{* }$ with endvertex v $v$ . This is a contradiction because G [ f ( H ) ] ∪ P ⊆ G $G[f(H)]\cup P\subseteq G$ contains a copy of T $T$ . Hence G v ${G}_{v}$ is X 1 ${{\mathscr{X}}}_{1}$ -free. G v ${G}_{v}$ is also X 2 ${{\mathscr{X}}}_{2}$ -free by Lemma 4.6(5) and X 3 ${{\mathscr{X}}}_{3}$ -free since v $v$ is the only vertex of colour 1 in G v ${G}_{v}$ . Lastly, we have d G ( v ) < k ${d}_{G}(v)\lt k$ by Lemma 4.6(3) and therefore

d G v ( v ) = d G ( v ) − d G * ( v ) ≤ k − d G * ( v ) − 1 = : n ′ ( v ) , ${d}_{{G}_{v}}(v)={d}_{G}(v)-{d}_{{G}^{* }}(v)\le k-{d}_{{G}^{* }}(v)-1=:n^{\prime} (v),$
which shows that G v ${G}_{v}$ is X 4 n ′ ( v ) ${{\mathscr{X}}}_{4}^{n^{\prime} (v)}$ -free. Therefore, there is a 2-embedding of G v ${G}_{v}$ in Γ n ′ ( v ) ${{\rm{\Gamma }}}^{n^{\prime} (v)}$ , and since G v ${G}_{v}$ is connected, there is an integer c ′ ( v ) ∈ N $c^{\prime} (v)\in {\mathbb{N}}$ such that the image of this 2-embedding is contained in Γ c ′ ( v ) n ′ ( v ) ${{\rm{\Gamma }}}_{c^{\prime} (v)}^{n^{\prime} (v)}$ .

Next, define an ω $\omega $ -colouring of G * ${G}^{* }$ by giving each vertex v ∈ V ( G * ) $v\in V({G}^{* })$ the colour c ′ ( v ) $c^{\prime} (v)$ . Since G * ${G}^{* }$ is S k ${S}_{k}$ -free by Lemma 4.6(3), Lemma 4.3 implies that there is a topological ω $\omega $ -embedding γ * ${\gamma }^{* }$ of G * ${G}^{* }$ in Γ * ${{\rm{\Gamma }}}^{* }$ with d G * ( v ) = d Γ * ( γ ( v ) ) ${d}_{{G}^{* }}(v)={d}_{{{\rm{\Gamma }}}^{* }}(\gamma (v))$ and hence n ′ ( v ) = n ( γ * ( v ) ) $n^{\prime} (v)=n({\gamma }^{* }(v))$ for all v ∈ V ( G * ) $v\in V({G}^{* })$ . For every vertex v ∈ V ( G * ) $v\in V({G}^{* })$ , we have c ′ ( v ) = c ( γ * ( v ) ) $c^{\prime} (v)=c({\gamma }^{* }(v))$ because γ $\gamma $ respects colouring. This means that Γ γ * ( v ) ${{\rm{\Gamma }}}_{{\gamma }^{* }(v)}$ is a copy of Γ c ′ ( v ) n ′ ( v ) ${{\rm{\Gamma }}}_{c^{\prime} (v)}^{n^{\prime} (v)}$ . Therefore, there exists a 2-embedding γ v ${\gamma }_{v}$ of G v ${G}_{v}$ in Γ v ${{\rm{\Gamma }}}_{v}$ and we have γ v ( v ) = γ * ( v ) ${\gamma }_{v}(v)={\gamma }^{* }(v)$ since γ v ${\gamma }_{v}$ respects colouring. Thus

γ * ∪ ⋃ v ∈ V ( G * ) γ v ${\gamma }^{* }\cup \bigcup _{v\in V({G}^{* })}{\gamma }_{v}$
is a topological embedding of G $G$ in Γ ${\rm{\Gamma }}$ . □ $\square $

5 FORBIDDEN SUBDIVIDED STARS—NEGATIVE RESULTS

In this section, we prove that there is no ⊴ $\unicode{x022B4}$ -universal T $T$ -free graph if T $T$ is a subdivided star in which at least 3 of the original edges are subdivided. The proof relies on ideas from Cherlin and Shelah in [1, Proposition 3.3].

Theorem 5.1.Let k ∈ N $k\in {\mathbb{N}}$ and p 1 ≤ ⋯ ≤ p k ∈ ℕ ${p}_{1}\le \cdots \,\le {p}_{k}\in {\rm{{\mathbb{N}}}}$ . If k ≥ 3 $k\ge 3$ and p k − 2 ≥ 2 ${p}_{k-2}\ge 2$ , then there exists no ⊴ $\unicode{x022B4}$ -universal graph in Forb ( T ( p 1 , … , p k ) ; ≤ ) $\text{Forb}(T({p}_{1},\ldots ,{p}_{k});\le )$ .

Proof.Let T ≔ T ( p 1 , … , p k ) $T:= T({p}_{1},\ldots ,{p}_{k})$ and let P 1 , … , P k ${P}^{1},\ldots ,{P}^{k}$ be the corresponding paths from Definition 4.1. Let m $m$ be minimal with p m > 1 ${p}_{m}\gt 1$ and define n ≔ k − m + 1 $n:= k-m+1$ . Then exactly n $n$ of the paths P 1 , … , P k ${P}^{1},\ldots ,{P}^{k}$ have length at least p m ${p}_{m}$ and the other paths have length 1.

Let H 1 ${H}_{1}$ be the graph consisting of two vertices x 1 ${x}_{1}$ and x 2 ${x}_{2}$ together with infinitely many independent x 1 ${x}_{1}$ – x 2 ${x}_{2}$ paths of length p m ${p}_{m}$ and let H 2 ${H}_{2}$ be the graph with vertex set { x 1 , x 2 , y 1 , y 2 , … , y p m } $\{{x}_{1},{x}_{2},{y}_{1},{y}_{2},\ldots ,{y}_{{p}_{m}}\}$ where every two vertices are adjacent except for x 1 ${x}_{1}$ and x 2 ${x}_{2}$ .

We use H 1 ${H}_{1}$ and H 2 ${H}_{2}$ to construct an uncountable family of T $T$ -free graphs. Consider the uncountable set A ⊆ { 1 , 2 } N $A\subseteq {\{1,2\}}^{{\mathbb{N}}}$ of all sequences that alternatingly contain one or two 1's and one 2, beginning with a 1. For all α ∈ A $\alpha \in A$ , let U α ${U}_{\alpha }$ be an ( n − 1 ) $(n-1)$ -regular tree with root r α ${r}_{\alpha }$ . For each edge v w ∈ E ( U α ) $vw\in E({U}_{\alpha })$ , we denote the minimum of d U α ( r α , v ) ${d}_{{U}_{\alpha }}({r}_{\alpha },v)$ and d U α ( r α , w ) ${d}_{{U}_{\alpha }}({r}_{\alpha },w)$ by ℓ ( v w ) $\ell (vw)$ . For all α ∈ A $\alpha \in A$ , we define a graph G α ${G}_{\alpha }$ as follows: We begin with U α ${U}_{\alpha }$ , replace every edge v w ∈ E ( U α ) $vw\in E({U}_{\alpha })$ with a copy of H α ( ℓ ( v w ) ) ${H}_{\alpha (\ell (vw))}$ , and identify x 1 ${x}_{1}$ with v $v$ and x 2 ${x}_{2}$ with w $w$ (see Figure 3). Note that for every vertex v ∈ V ( U α ) $v\in V({U}_{\alpha })$ there is at least one edge e ∈ E ( U α ) $e\in E({U}_{\alpha })$ which was replaced by a copy of H 1 ${H}_{1}$ . Hence v $v$ has infinite degree in G α ${G}_{\alpha }$ . □ $\square $

Details are in the caption following the image
Figure 3
Open in figure viewerPowerPoint
The graph G α ${G}_{\alpha }$ when p m = 2 , n = 4 ${p}_{m}=2,n=4$ and α = ( 1 , 1 , 2 , … ) $\alpha =(1,1,2,\ldots )$ . The fat edges form a subdivision of U α ${U}_{\alpha }$ in G α ${G}_{\alpha }$ .

We now prove two crucial properties of G α ${G}_{\alpha }$ for all α ∈ A $\alpha \in A$ :

Claim 1. G α ${G}_{\alpha }$ is T $T$ -free.

Proof of Claim 1.Suppose that there is a copy of T $T$ in G α ${G}_{\alpha }$ and let v $v$ be its centre. It is impossible that v ∈ V ( G α ) ⧹ V ( U α ) $v\in V({G}_{\alpha })\setminus V({U}_{\alpha })$ : If v $v$ is contained in a copy of H 1 ${H}_{1}$ , then the degree of v $v$ in G α ${G}_{\alpha }$ is 2 and therefore v $v$ cannot be the centre of a copy of T $T$ . Now suppose that v $v$ is contained in a copy of H 2 ${H}_{2}$ . The copy of T $T$ contains three paths of length at least p m ${p}_{m}$ starting in v $v$ . Each of them has at least p m + 1 ${p}_{m}+1$ vertices and must therefore use one of the vertices corresponding to x 1 ${x}_{1}$ or x 2 ${x}_{2}$ in the copy of H 2 ${H}_{2}$ which is a contradiction. Therefore, v $v$ must be contained in V ( U α ) $V({U}_{\alpha })$ . However, v $v$ is only contained in n − 1 $n-1$ copies of H 1 ${H}_{1}$ or H 2 ${H}_{2}$ and each of them can only contain inner vertices of at most one of the paths P i ${P}^{i}$ for i ≥ m $i\ge m$ , a contradiction. □ $\square $

Claim 2.Every subdivision G α ′ ${G}_{\alpha }^{^{\prime} }$ of G α ${G}_{\alpha }$ with at least one subdividing vertex v $v$ contains a subgraph isomorphic to T $T$ .

Proof of Claim 2.Let H $H$ be the subdivision of a copy of H i ${H}_{i}$ for i = 1 $i=1$ or i = 2 $i=2$ in G α ′ ${G}_{\alpha }^{^{\prime} }$ which contains v $v$ and let γ $\gamma $ be a topological embedding of H i ${H}_{i}$ in H $H$ . Then we can find an embedding of T $T$ in G α ′ ${G}_{\alpha }^{^{\prime} }$ as follows. We map the centre of T $T$ to γ ( x 1 ) $\gamma ({x}_{1})$ , and P m ${P}^{m}$ to a path of length p m ${p}_{m}$ in H $H$ containing v $v$ but not γ ( x 2 ) $\gamma ({x}_{2})$ , and P i ${P}^{i}$ for i > m $i\gt m$ to paths each containing one neighbour of γ ( x 1 ) $\gamma ({x}_{1})$ in U α ${U}_{\alpha }$ . Since γ ( x 1 ) $\gamma ({x}_{1})$ is contained in V ( U α ) $V({U}_{\alpha })$ , it has infinite degree in G α ${G}_{\alpha }$ and thus also in G α ′ ${G}_{\alpha }^{^{\prime} }$ . Therefore it is easy to embed the paths P i ${P}^{i}$ for i < m $i\lt m$ in G α ′ ${G}_{\alpha }^{^{\prime} }$ . □ $\square $

Suppose for a contradiction that Γ ${\rm{\Gamma }}$ is a ⊴ $\unicode{x022B4}$ -universal graph in Forb ( T ; ≤ ) $\text{Forb}(T;\le )$ . For all α ∈ A $\alpha \in A$ , we have G α ⊴ Γ ${G}_{\alpha }\,\unicode{x022B4}\,{\rm{\Gamma }}$ by Claim 1 and therefore G α ≤ Γ ${G}_{\alpha }\le {\rm{\Gamma }}$ by Claim 2. We will show that this is impossible.

We define a symmetric binary relation R $R$ on the vertices of Γ ${\rm{\Gamma }}$ such that R ( v , w ) $R(v,w)$ if and only if Γ ${\rm{\Gamma }}$ contains a subgraph isomorphic to H 1 ${H}_{1}$ or H 2 ${H}_{2}$ where v $v$ and w $w$ play the roles of x 1 ${x}_{1}$ and x 2 ${x}_{2}$ , respectively.

Claim 3.Let α ∈ A $\alpha \in A$ and suppose that G α ⊆ Γ ${G}_{\alpha }\subseteq {\rm{\Gamma }}$ . If u ∈ V ( G α ) $u\in V({G}_{\alpha })$ is a vertex that is contained in V ( U α ) $V({U}_{\alpha })$ and v ∈ V ( Γ ) $v\in V({\rm{\Gamma }})$ is any vertex, then R ( u , v ) $R(u,v)$ implies that also v ∈ V ( U α ) $v\in V({U}_{\alpha })$ and that u $u$ and v $v$ are adjacent in U α ${U}_{\alpha }$ .

Proof of Claim 3.Let α ∈ A $\alpha \in A$ be given and write G ≔ G α $G:= {G}_{\alpha }$ and U ≔ U α $U:= {U}_{\alpha }$ . First, note that G $G$ contains a subdivision U ′ $U^{\prime} $ of U $U$ (see Figure 3). We claim that the following is true:

  • (1)

    If a ≠ b ∈ V ( U ) $a\ne b\in V(U)$ are adjacent in Γ ${\rm{\Gamma }}$ , then a $a$ and b $b$ are also adjacent in U $U$ and we have α ( ℓ ( a , b ) ) = 1 $\alpha (\ell (a,b))=1$ (which means that there is a copy of H 1 ${H}_{1}$ in G $G$ between a $a$ and b $b$ ).

  • (2)

    If a ≠ b ∈ V ( U ) , c ∈ V ( Γ ) ⧹ V ( U ) $a\ne b\in V(U),c\in V({\rm{\Gamma }})\setminus V(U)$ , and a c , c b ∈ E ( Γ ) $ac,cb\in E({\rm{\Gamma }})$ , then a $a$ and b $b$ are adjacent in U $U$ .

For the proof of (1), first suppose that a $a$ and b $b$ are not adjacent in U $U$ . Then G + a b ⊆ Γ $G+ab\subseteq {\rm{\Gamma }}$ contains a copy of T $T$ with centre a $a$ which is a contradiction: Let a ′ $a^{\prime} $ be the neighbour of a $a$ in U $U$ which lies on the a $a$ – b $b$ path in U $U$ . We embed P m ${P}^{m}$ in the copy of H 1 ${H}_{1}$ or H 2 ${H}_{2}$ which we inserted for the edge a a ′ $aa^{\prime} $ in G $G$ and P i ${P}^{i}$ for i > m $i\gt m$ in U ′ + a b $U^{\prime} +ab$ . It is easy to embed P i ${P}^{i}$ for i < m $i\lt m$ since a $a$ has infinite degree in G $G$ . Thus a $a$ and b $b$ are adjacent in U $U$ . Now suppose that α ( ℓ ( a , b ) ) = 2 $\alpha (\ell (a,b))=2$ and let γ $\gamma $ be a topological embedding of H 2 ${H}_{2}$ in G $G$ with γ ( x 1 ) = a $\gamma ({x}_{1})=a$ and γ ( x 2 ) = b $\gamma ({x}_{2})=b$ . However, then we can find a copy of T $T$ in Γ ${\rm{\Gamma }}$ with centre a $a$ by embedding P m ${P}^{m}$ in the path a γ ( y 1 ) … γ ( y p m ) $a\gamma ({y}_{1})\,\ldots \,\gamma ({y}_{{p}_{m}})$ and P i ${P}^{i}$ for i > m $i\gt m$ into U ′ + a b $U^{\prime} +ab$ . Again it is easy to embed P i ${P}^{i}$ for i < m $i\lt m$ . The proof of (2) is similar, we only have to choose U ′ $U^{\prime} $ so that c ∉ V ( U ′ ) $c\notin V(U^{\prime} )$ .

For the proof of Claim 3, we begin with the case that R ( u , v ) $R(u,v)$ witnessed by a subgraph of Γ ${\rm{\Gamma }}$ isomorphic to H 1 ${H}_{1}$ such that u $u$ and v $v$ play the roles of x 1 ${x}_{1}$ and x 2 ${x}_{2}$ in H 1 ${H}_{1}$ , respectively. Then v $v$ must lie in V ( U ′ ) $V(U^{\prime} )$ because otherwise we can find a copy of T $T$ in Γ ${\rm{\Gamma }}$ with centre u $u$ : We embed all paths P i ${P}^{i}$ with i > m $i\gt m$ in U ′ $U^{\prime} $ and P m ${P}^{m}$ in one of the infinitely many u $u$ – v $v$ paths which avoids P i − u ${P}^{i}-u$ for all i > m $i\gt m$ . Therefore, we can assume that v ∈ V ( U ′ ) $v\in V(U^{\prime} )$ and that we cannot find a different subdivision U ″ $U^{\prime\prime} $ of U $U$ in G $G$ with v ∉ V ( U ″ ) $v\notin V(U^{\prime\prime} )$ . Hence v ∈ V ( U ) $v\in V(U)$ . Suppose for a contradiction that u $u$ and v $v$ are not adjacent in U $U$ and choose U ′ $U^{\prime} $ so that d U ′ ( u , v ) > p m ${d}_{U^{\prime} }(u,v)\gt {p}_{m}$ . However, then we can find a copy of T $T$ in Γ ${\rm{\Gamma }}$ with centre u $u$ by embedding P i ${P}^{i}$ for m ≤ i < k $m\le i\lt k$ in U ′ − v $U^{\prime} -v$ and P k ${P}^{k}$ in the union of U ′ $U^{\prime} $ with a u $u$ – v $v$ path in Γ ${\rm{\Gamma }}$ avoiding P i − u ${P}^{i}-u$ for all m ≤ i < k $m\le i\lt k$ .

Otherwise we have R ( u , v ) $R(u,v)$ because H 2 ≤ Γ ${H}_{2}\le {\rm{\Gamma }}$ , witnessed by an embedding f $f$ of H 2 ${H}_{2}$ in Γ ${\rm{\Gamma }}$ such that f ( x 1 ) = u $f({x}_{1})=u$ and f ( x 2 ) = v $f({x}_{2})=v$ . Additionally, we may assume that there is no such embedding of H 1 ${H}_{1}$ in Γ ${\rm{\Gamma }}$ . We begin by showing that we can assume that V ( U ) $V(U)$ contains none of the vertices f ( y 1 ) , … , f ( y p m − 1 ) $f({y}_{1}),\ldots ,f({y}_{{p}_{m}-1})$ . Suppose that there are i ≠ j $i\ne j$ with f ( y i ) , f ( y j ) ∈ V ( U ) $f({y}_{i}),f({y}_{j})\in V(U)$ . Then u f ( y i ) , u f ( y j ) , f ( y i ) f ( y j ) ∈ E ( U ) $uf({y}_{i}),uf({y}_{j}),f({y}_{i})f({y}_{j})\in E(U)$ by (1), which is impossible because U $U$ is a tree. Therefore at most one of the vertices f ( y 1 ) , … , f ( y p m ) $f({y}_{1}),\ldots ,f({y}_{{p}_{m}})$ can lie in V ( U ) $V(U)$ , without loss of generality f ( y 1 ) , … , f ( y p m − 1 ) ∉ V ( U ) $f({y}_{1}),\ldots ,f({y}_{{p}_{m}-1})\notin V(U)$ .

If v ∈ V ( U ) $v\in V(U)$ we can show that u $u$ and v $v$ are adjacent in U $U$ , as required in Claim 3: Since f ( y 1 ) ∉ V ( U ) $f({y}_{1})\notin V(U)$ and the edges u f ( y 1 ) $uf({y}_{1})$ and f ( y 1 ) v $f({y}_{1})v$ are contained in E ( Γ ) $E({\rm{\Gamma }})$ , it follows from (2) that u $u$ and v $v$ are adjacent in U $U$ . It is left to show that v ∉ V ( U ) $v\notin V(U)$ is impossible.

Finally, we demonstrate that v , f ( y 1 ) , … , f ( y p m − 1 ) ∉ V ( U ) $v,f({y}_{1}),\ldots ,f({y}_{{p}_{m}-1})\notin V(U)$ leads to a contradiction. We begin by showing that we can always choose U ′ $U^{\prime} $ so that it contains none of the vertices v , f ( y 1 ) , … , f ( y p m − 1 ) $v,f({y}_{1}),\ldots ,f({y}_{{p}_{m}-1})$ . There is only one case in which this is impossible: We must have H 2 ≤ G ${H}_{2}\le G$ , witnessed by an embedding g $g$ of H 2 ${H}_{2}$ in G $G$ such that { v , f ( y 1 ) , … , f ( y p m − 1 ) } = { g ( y 1 ) , … , g ( y p m ) } $\{v,f({y}_{1}),\ldots ,f({y}_{{p}_{m}-1})\}=\{g({y}_{1}),\ldots ,g({y}_{{p}_{m}})\}$ . First we notice that f ( y p m ) ∈ V ( U ) $f({y}_{{p}_{m}})\in V(U)$ , as otherwise we can find a copy of T $T$ in Γ ${\rm{\Gamma }}$ with centre g ( x 1 ) $g({x}_{1})$ by embedding P m ${P}^{m}$ in the path g ( x 1 ) g ( y 2 ) g ( y 3 ) … g ( y p m ) f ( y p m ) $g({x}_{1})g({y}_{2})g({y}_{3})\ldots g({y}_{{p}_{m}})f({y}_{{p}_{m}})$ and P i ${P}^{i}$ for i > m $i\gt m$ into a subdivision of U $U$ in G $G$ containing g ( y 1 ) $g({y}_{1})$ . Furthermore, since u f ( y p m ) ∈ E ( Γ ) $uf({y}_{{p}_{m}})\in E({\rm{\Gamma }})$ , (1) implies that there is a vertex w ∈ { u , f ( y p m ) } $w\in \{u,f({y}_{{p}_{m}})\}$ which is not an element of { g ( x 1 ) , g ( x 2 ) } $\{g({x}_{1}),g({x}_{2})\}$ . The edges w f ( y 1 ) $wf({y}_{1})$ and f ( y 1 ) g ( x i ) $f({y}_{1})g({x}_{i})$ are contained in E ( Γ ) $E({\rm{\Gamma }})$ for i = 1 , 2 $i=1,2$ and thus (2) implies that w $w$ and g ( x i ) $g({x}_{i})$ are adjacent in U $U$ . However, it follows that g ( x 1 ) , g ( x 2 ) $g({x}_{1}),g({x}_{2})$ and w $w$ induce a triangle in the tree U $U$ . Hence we can assume that U ′ $U^{\prime} $ does not contain v , f ( y 1 ) , … , f ( y p m − 1 ) $v,f({y}_{1}),\ldots ,f({y}_{{p}_{m}-1})$ . But now we can find a copy of T $T$ with centre u $u$ in the union of U ′ $U^{\prime} $ with the path u f ( y 1 ) … f ( y p m − 1 ) v $uf({y}_{1})\ldots f({y}_{{p}_{m}-1})v$ in Γ ${\rm{\Gamma }}$ , a contradiction. □ $\square $

For all α ∈ A $\alpha \in A$ let γ α ${\gamma }_{\alpha }$ be an embedding of G α ${G}_{\alpha }$ in Γ ${\rm{\Gamma }}$ and define D α i ≔ { v ∈ V ( U α ) : d U α ( r α , v ) = i } ${D}_{\alpha }^{i}:= \{v\in V({U}_{\alpha }):{d}_{{U}_{\alpha }}({r}_{\alpha },v)=i\}$ for all i ∈ N $i\in {\mathbb{N}}$ . Since A $A$ is uncountable but Γ ${\rm{\Gamma }}$ is countable, there exist α ≠ α ′ ∈ A $\alpha \ne \alpha ^{\prime} \in A$ such that γ α ( r α ) = γ α ′ ( r α ′ ) ${\gamma }_{\alpha }({r}_{\alpha })={\gamma }_{\alpha ^{\prime} }({r}_{\alpha ^{\prime} })$ . Without loss of generality, we assume that G α , G α ′ ⊆ Γ ${G}_{\alpha },{G}_{\alpha ^{\prime} }\subseteq {\rm{\Gamma }}$ (and not just G α , G α ′ ≤ Γ ${G}_{\alpha },{G}_{\alpha ^{\prime} }\le {\rm{\Gamma }}$ ). By Claim 3, we have D α i = D α ′ i ${D}_{\alpha }^{i}={D}_{\alpha ^{\prime} }^{i}$ for all i ∈ N $i\in {\mathbb{N}}$ . Since α ≠ α ′ $\alpha \ne \alpha ^{\prime} $ , it follows that there are embeddings f : H 1 → G α ⊆ Γ $f:{H}_{1}\to {G}_{\alpha }\subseteq {\rm{\Gamma }}$ and g : H 2 → G α ′ ⊆ Γ $g:{H}_{2}\to {G}_{\alpha ^{\prime} }\subseteq {\rm{\Gamma }}$ such that f ( x 1 ) = g ( x 1 ) $f({x}_{1})=g({x}_{1})$ and f ( x 2 ) = g ( x 2 ) $f({x}_{2})=g({x}_{2})$ (we might have to swap the roles of α $\alpha $ and α ′ $\alpha ^{\prime} $ for that).

The vertices g ( y 1 ) , … , g ( y p m ) $g({y}_{1}),\ldots ,g({y}_{{p}_{m}})$ are not contained in any copy of H 2 ${H}_{2}$ in G α ${G}_{\alpha }$ : Suppose for a contradiction that, for example, g ( y 1 ) $g({y}_{1})$ is contained in a copy H 2 ′ ${H}_{2}^{^{\prime} }$ of H 2 ${H}_{2}$ in G α ${G}_{\alpha }$ . Note that g ( y 1 ) , … , g ( y p m ) ∉ V ( U α ′ ) = V ( U α ) $g({y}_{1}),\ldots ,g({y}_{{p}_{m}})\notin V({U}_{\alpha ^{\prime} })=V({U}_{\alpha })$ . Furthermore, g ( y 1 ) $g({y}_{1})$ is adjacent to g ( x 1 ) = f ( x 1 ) $g({x}_{1})=f({x}_{1})$ and g ( x 2 ) = f ( x 2 ) $g({x}_{2})=f({x}_{2})$ and to vertices y , z $y,z$ that play the role of x 1 , x 2 ${x}_{1},{x}_{2}$ in H 2 ′ ${H}_{2}^{^{\prime} }$ . Hence { f ( x 1 ) , f ( x 2 ) } ≠ { y , z } $\{f({x}_{1}),f({x}_{2})\}\ne \{y,z\}$ and therefore g ( y 1 ) $g({y}_{1})$ is adjacent to at least three distinct vertices from V ( U α ) $V({U}_{\alpha })$ . Then by (2) we can find a triangle in U α ${U}_{\alpha }$ , a contradiction.

Let U ′ ⊆ G α $U^{\prime} \subseteq {G}_{\alpha }$ be a subdivision of U α ${U}_{\alpha }$ . Since g ( y 1 ) , … , g ( y p m ) $g({y}_{1}),\ldots ,g({y}_{{p}_{m}})$ are not contained in any copy of H 2 ${H}_{2}$ in G α ${G}_{\alpha }$ and g ( y 1 ) , … , g ( y p m ) ∉ V ( U α ) $g({y}_{1}),\ldots ,g({y}_{{p}_{m}})\notin V({U}_{\alpha })$ , we can choose U ′ $U^{\prime} $ so that it contains none of the vertices g ( y 1 ) , … , g ( y p m ) $g({y}_{1}),\ldots ,g({y}_{{p}_{m}})$ . However, the union of U ′ $U^{\prime} $ with the path g ( x 1 ) g ( y 1 ) … g ( y p m ) $g({x}_{1})g({y}_{1})\,\ldots \,g({y}_{{p}_{m}})$ contains a copy of T $T$ . Thus a ⊴ $\unicode{x022B4}$ -universal graph Γ ${\rm{\Gamma }}$ in Forb ( T ; ≤ ) $\text{Forb}(T;\le )$ cannot exist.

Proof of Theorem 1.4.We combine Theorems 4.2 and 5.1. □ $\square $

ACKNOWLEDGEMENTS

Open Access funding enabled and organized by Projekt DEAL.

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