# On graph classes with minor-universal elements

Agelos Georgakopoulos Supported by EPSRC grants EP/V048821/1 and EP/V009044/1.
Mathematics Institute, University of Warwick
CV4 7AL, UK

###### Abstract

A graph $U$ is universal for a graph class $\mathcal{C}\ni U$, if every
$G\in\mathcal{C}$ is a minor of $U$. We prove the existence or absence of
universal graphs in several natural graph classes, including graphs component-
wise embeddable into a surface, and graphs forbidding $K_{5}$, or $K_{3,3}$,
or $K_{\infty}$ as a minor. We prove the existence of uncountably many minor-
closed classes of countable graphs that (do and) do not have a universal
element.

Some of our results and questions may be of interest to the finite graph
theorist. In particular, one of our side-results is that every $K_{5}$-minor-
free graph is a minor of a $K_{5}$-minor-free graph of maximum degree 22.

Keywords: Universal graph, infinite graph, minor-closed, excluded minor,
graphs in surfaces,

MSC 2020 Classification: 05C99, 05C83, 05C10.

##  1 Introduction

Given a binary relation $\prec$ between graphs —typically the (induced)
subgraph or minor relation— we say that a graph $U$ is $\prec$-universal for a
graph class $\mathcal{C}\ni U$, if $G\prec U$ holds for every
$G\in\mathcal{C}$. (It is often, but not always, the case that $\mathcal{C}$
is closed under $\prec$.)

The study of universal graphs is one of the oldest topics of infinite graph
theory. The best known instance is the Rado graph [22], an induced-subgraph-
universal countable graph. Diestel, Halin & Vogler [2] proved that there is no
subgraph-universal graph in the class of countable graphs with no $K_{n}$
minor for $5\leq n\leq\aleph_{0}$, but there is one for $n\leq 4$.

Pach [20] proved that there is no subgraph-universal planar graph. Huynh et
al. [10] recently strengthened this by showing that if $G$ contains every
countable planar graph as a subgraph then it must have the infinite complete
graph $K_{\infty}$ as a minor. Lehner [17] strengthened this further by
showing that the same conclusion holds if $G$ contains every countable planar
graph as a topological minor.

For more background about universal graphs we refer to e.g. [9, 12, 14, 15]
and the survey [13].

This paper studies $<$-universal graphs, where $<$ stands for the minor
relation, with an emphasis on interactions with the finite graph minor theory.
Despite Pach’s result and its aforementioned strengthenings, Diestel and Kühn
proved

######  Theorem 1.1 ([3]).

There is a $<$-universal countable planar graph.

Theorem 1.1 provides motivation as well an important tool for this paper.
Other natural minor-closed classes known so far to have minor-universal
elements are forests, series-parallel graphs [2], outer-planar graphs [3], and
graphs with accumulation-free embeddings in $\mathbb{R}^{2}$ [15]. Diestel &
Kühn [3] asked

######  Question 1.1.

Which minor-closed graph classes have a countable $<$-universal element?

They specifically discussed the special cases of Question 1.1 for the classes
$Forb(K_{5})$ and $Forb(K_{\infty})$. This paper settles these two cases of
Question 1.1, as well as many more. Our first result is easy to explain, and
it adapts a well-known idea ([13, Proposition 3.2.]):

######  Theorem 1.2.

The class of countable $K_{\infty}$-minor-free graphs has no $<$-universal
element.

###### Proof.

Suppose $U$ is a universal $K_{\infty}$-minor-free graph. Add a new vertex
$v^{*}$, and join it with an edge to each vertex of $U$ to obtain a new graph
$C(U)$. Notice that $C(U)$ is still $K_{\infty}$-minor-free, and therefore we
can find $C(U)$ as a minor $M$ of $U$. Let $B_{0}$ be the branch set of such a
minor corresponding to $v^{*}$. Thus $U$ is a minor of $U\backslash B_{0}$,
hence the latter is still universal. Repeat the argument to find a minor of
$U\backslash B_{0}$ isomorphic to $C(U)$ every branch set of which contains
one of $M$, and let $B_{1}$ be the new branch set corresponding to $v^{*}$.
Repeat ad infinitum to define $(B_{n})_{n\in\mathbb{N}}$, and notice that each
$B_{i}$ sends an edge to all $B_{j},j>i$. Thus the $B_{i}$ form the branch
sets of a $K_{\infty}$ minor in $U$, which is a contradiction. ∎

We remark that the class of $K_{\infty}$-minor-free graphs had attracted a lot
of attention, and alternative characterizations are known [4, 23, 27].

A second look at the above proof reveals that the choice of the forbidden
minor $K_{\infty}$ is not too important; the same argument can be applied if
we replace $K_{\infty}$ by any graph $G\ $that is a minor of $G-v$ for every
$v\in V(G)$. This yields

######  Corollary 1.3.

Let $G\ $be a graph such that $G<G-v$ holds for every $v\in V(G)$. Then the
class of $G$-minor-free graphs has no $<$-universal element. ∎

Examples of such $G\ $include the ray, the half- and full-grid, and any graph
which is a disjoint union of infinitely many copies of a fixed graph $H$.
Letting $G\ $be the ray, we thus strengthen a result of Diestel, Halin &
Vogler [2, Theorem 4.1] saying that there is no subgraph-universal graph in
the class of countable rayless graphs.

C. Thomassen observed that for every closed surface $\Sigma$ other than
$\mathbb{S}^{2}$, the class $\mathcal{E}_{\Sigma}$ of countable graphs that
embed in $\Sigma$ has no $<$-universal element [3, § 6]. Our next result shows
that the reason for this lies in the lack of addability of
$\mathcal{E}_{\Sigma}$:

######  Theorem 1.4.

Let $\Sigma$ be a closed orientable surface, and let $\mathcal{C}_{\Sigma}$ be
the class of countable graphs $G$ such that every component of $G\ $embeds in
$\Sigma$. Then $\mathcal{C}_{\Sigma}$ has a $<$-universal element.

We prove Theorem 1.4 in Section 4 by combining the universal planar graph of
Diestel and Kühn [3] with a classical result of Youngs [31] about embeddings
of finite graphs. We will thereby introduce some handy tools for dealing with
infinite embedded graphs, simplifying one of the ingredients of the proof of
Theorem 1.1 in [3].

The other aforementioned question of Diestel and Kühn has a positive answer:

######  Theorem 1.5.

The class of countable graphs with no $K_{5}$ minor has a $<$-universal
element. So does the class of countable $K_{3,3}$-minor-free graphs.

This is the most difficult result of this paper. We prove it in Section 6,
using again the universal planar graph, combining it with Wagner’s clique-sum
decompositions of such graphs [30], as extended to the infinite case by Křìž &
Thomas [16].

Theorem 1.2 provides the simplest proof I am aware of for the fact that there
are uncountably many minor-twin classes of countable graphs: for if
$(G_{n})_{n\in\mathbb{N}}$ was a countable sequence representing them all,
then $\dot{\bigcup}_{n}G_{n}\backslash\\{K_{\infty}\\}$ would be a universal
$K_{\infty}$-minor-free graph.

Note that for every graph $G$, its minors $\mathcal{C}_{G}:=\\{H\mid H<G\\}$
form a minor-closed family which has $G$ as a $<$-universal element. In
Section 3 we will prove that there are uncountably many minor-closed classes
of countable graphs none of which classes has a $<$-universal element. This is
achieved by combining Corollary 1.3 with a beautiful result of Matthiesen
[18], which uses Nash-Williams’ theorem that trees are well-quasi-ordered to
deduce that there are uncountably many topological-minor-twin classes of
rooted trees.

To summarize, we have provided the following response to Question 1.1 which
perhaps answers it to the extent possible:

######  Theorem 1.6.

There are uncountably many minor-closed classes of countable graphs that do,
and uncountably many that do not have a $<$-universal element.

One can still propose refined versions of the question, e.g. asking for
sufficient conditions for the existence of a $<$-universal element. The
following question of this form is motivated by the above discussion on graphs
on surfaces and Corollary 1.3:

######  Problem.

Let $F_{1},\ldots,F_{k}$ be finite connected graphs. Must
$\mathrm{Forb}(F_{1},\ldots,F_{k})$ have a $<$-universal element?

We will discuss this problem further in Section 7, along with several other
open questions.

As a consequence of our proof of Theorem 1.5, we will obtain (in Section 6.1)
the following corollary, which as far as I am aware is new even for finite
graphs.

######  Corollary 1.7.

Every $K_{5}$-minor-free graph is a minor of a $K_{5}$-minor-free graph with
maximum degree 22. Every $K_{3,3}$-minor-free graph is a minor of a
$K_{3,3}$-minor-free graph with maximum degree 9.

See Section 6.1 for a proof and related questions. A proof of Corollary 1.7
for finite graphs that does not pass through the infinite can be extracted
from our methods, repeating about half of the work.

##  2 Preliminaries

###  2.1 Graphs

We follow the terminology of Diestel [5]. We use $V(G)$ to denote the set of
vertices, and $E(G)$ the set of edges of a graph $G$. For $S\subseteq V(G)$,
the subgraph $G[S]$ of $G\ $_induced_ by $S$ has vertex set $S$ and contains
all edges of $G\ $with both endvertices in $S$.

The _degree_ $d(v)=d_{G}(v)$ of a vertex $v$ in a graph $G$, is the number of
edges of $G\ $incident with $v$. The _maximum degree_ $\Delta(G)$ of $G\ $is
$\sup_{v\in V(G)}d(v)$. The _closed neighbourhood_ of $v\in V(G)$ is the
subgraph of $G\ $induced by $v$ and all its _neighbours_ , i.e. the vertices
sharing an edge with $v$.

We write $G\dot{\cup}H$ for the disjoint union of two graphs $G,H$, and
$\omega\cdot G$ for the disjoint union of countably infinitely many copies of
$G$.

A _ray_ is a one-way infinite path.

###  2.2 Embeddings

A _surface_ is a 2-manifold without boundary. An _embedding_ of a countable
graph $G\ $ into a surface $\Sigma$ is a map $f:G\to\Sigma$ from the 1-complex
obtained from $G\ $when identifying each edge with the interval $[0,1]$ to
$\Sigma$ such that the restriction of $f$ to each finite subgraph of $G$ is an
embedding in the topological sense, i.e. a homeomorphism onto its image. (The
reason why we restrict to finite subgraphs here is that the 1-complex topology
of $G\ $is not metrizable when $G\ $is not locally finite, and so such $G\
$cannot have an embedding into a metrizable space $\Sigma$. For example, a
star with infinitely many leaves admits an embedding into $\mathbb{S}^{2}$ in
our sense but it does not admit a topological embedding.)

A _face_ of an embedding $f:G\to\Sigma$ is a component of $\Sigma\backslash
f(G)$. A _facial walk_ is a (finite, or two-way infinite) sequence $\ldots
v_{0}e_{0}v_{1}e_{1}\ldots$ of vertices and edges of $G\ $whose $f$-images
appear along the boundary of a face of $f$ in that order.

The _(orientable) genus_ $\gamma(G)$ of a graph $G\ $is the smallest genus
$\gamma(\Sigma)$ of an orientable surface $\Sigma$ into which $G\ $embeds.

###  2.3 Minors

Let $G,H$ be graphs. An $H$-_minor_ of $G$ is a collection of disjoint
connected subgraphs $B_{v},v\in V(H)$ of $G$, called _branch sets_ , and edges
$E_{uv},uv\in E(H)$ of $G\ $such that each $E_{uv}$ has one end-vertex in
$B_{u}$ and one in $B_{v}$. We write $H<G$ to express that $G$ has an $H$
minor.

We say that $G$ and $H$ are _minor-twins_ , if both $G<H$ and $H<G$ hold. Any
two finite minor-twins are isomorphic, but in the infinite case it is often
helpful to think in terms of equivalence classes of minor-twins instead of
isolated graphs.

Given a set $X$ of graphs, we write $\mathrm{Forb}(X)$ for the class of graphs
$H$ such that no element of $X$ is a minor of $H$. For a minor-closed graph
class $\mathcal{C}$, we write $\mathrm{Ex}(\mathcal{C})$ for the set of graphs
$G$ such that $G\not\in\mathcal{C}$ but $H\in\mathcal{C}$ for every $H<G$ such
that $G\not<H$. If $\mathcal{C}$ consists of finite graphs, then
$\mathrm{Forb}(\mathrm{Ex}(\mathcal{C}))=\mathcal{C}$ holds by the
definitions. For infinite graphs this will fail if there is an infinite
descending sequence $G_{1}>G_{2}>\ldots$ (consisting of graphs not in
$\mathcal{C}$) which as far as I know is open [28].

##  3 Uncountably many classes with no $<$-universal element

The aim of this section is to prove

######  Proposition 3.1.

There are uncountably many classes of countable graphs that have no
$<$-universal element.

To begin with, recall that Theorem 1.2 implies that there are uncountably many
minor-twin classes of countable graphs.

As we will see, one can find uncountably many minor-twin classes among much
more restricted classes of graphs using the following result of Matthiesen.

The _tree-order_ $\leq$ on the set of vertices of a rooted tree $(T,r)$ is
defined by setting $x\leq y$ whenever $x$ lies on the unique path in $T$ from
its root $r$ to $y$. Given two rooted trees $(T,r),(T^{\prime},r^{\prime})$,
we write $(T,r)<_{\leq}(T^{\prime},r^{\prime})$ if there is an embedding
$t:(T,r)\to(T^{\prime},r^{\prime})$ that respects the tree-order when
restricted to $V(T)$.

######  Theorem 3.2 ([18]).

There are uncountably many equivalence classes of locally finite rooted trees
with respect to the order-preserving topological minor relation $<_{\leq}$.
This remains true in the class of rooted trees every vertex of which has at
most two successors.

Theorem 3.2 provides another way for proving that there are uncountably many
minor-twin classes of countable graphs: let $\mathcal{T}$ be an uncountable
family of rooted trees no two of which are in the same equivalence class of
$<_{\leq}$ as provided by Theorem 3.2, and attach a triangle to the root of
each member of $\mathcal{T}$. The resulting family of (unrooted) graphs
contains no pair of minor-twins. We leave the details to the reader as a warm-
up exercise before the following proof.

###### Proof of Proposition 3.1.

Let $\mathcal{T}$ be an uncountable family of rooted trees as provided by
Theorem 3.2, i.e. such that no two elements are equivalent with respect to
$<_{\leq}$, and every vertex of each $T\in\mathcal{T}$ has at most two
successors in $\leq$.

Our plan is to associate to each $T\in\mathcal{T}$ a graph class
$\mathcal{C}_{T}$, defined by forbidding a relative of $T$ as a minor, such
that $\mathcal{C}_{T}$ has no $<$-universal element by Corollary 1.3. But as
$T$ does not have to satisfy the premise of Corollary 1.3, we introduce a
graph $T^{\prime}$ that does using the construction of Figure 1. To make this
precise, we start with a ray $R=R_{T}=r_{1}r_{2}\ldots$, and attach a new edge
$e_{i}=r_{i}v_{i}$ to the $i$th vertex of $R$ for every $i\in\mathbb{N}$.
Then, for every even $i$, we attach a triangle to $v_{i}$, and for every odd
$i$, we attach a copy of $T$ identifying the root of $T$ with $v_{i}$. Let
$\mathcal{T}^{\prime}:=\\{T^{\prime}\mid T\in\mathcal{T}\\}$.

\begin{overpic}[width=238.49231pt]{figTp2} \put(2.0,16.0){$r_{0}$}
\put(13.0,24.0){$r_{1}$} \put(24.0,16.0){$r_{2}$} \put(73.0,23.0){$R$}
\put(12.5,3.0){$T$} \put(33.0,3.0){$T$} \put(53.5,3.0){$T$} \end{overpic}
Figure 1: The construction of $T^{\prime}$.

We claim that

$\mathcal{T}^{\prime}$ contains no pair of minor-twins. (1)

We emphasize that $\mathcal{T}^{\prime}$ is a family of graphs with no
designated root, and (1) refers to the standard notion of minor, with no
reference to $<_{\leq}$.

Once (1) is proven, the above idea can be easily carried out: we define the
graph classes $\mathcal{C}(T):=Forb(T^{\prime}),T\in\mathcal{T}$. They are all
distinct by (1), and uncountably many. Note that $T^{\prime}$ embeds into its
subgraph to the right of an arbitrary $r_{i}$ of $R_{T}$, and therefore
$T^{\prime}$ satisfies the premise of Corollary 1.3, from which we deduce that
$\mathcal{C}(T)$ has no $<$-universal element.

To prove (1), suppose that $T^{\prime}_{1}<T^{\prime}_{2}$ for some
$T^{\prime}_{1},T^{\prime}_{2}\in\mathcal{T}^{\prime}$. We will deduce that
$T_{1}<_{\leq}T_{2}$. This immediately implies (1), as $T_{1},T_{2}$ cannot be
twins with respect to $<_{\leq}$.

To see the latter claim, note first that as all our graphs have maximum degree
3, we can find a topological $T^{\prime}_{1}$ minor in $T^{\prime}_{2}$, i.e.
an embedding $g:T^{\prime}_{1}\to T^{\prime}_{2}$. Next, we note that
$g(R_{T_{1}})$ must contain all but finitely many edges of $R_{T_{2}}$,
because otherwise $g(R_{T_{1}})$ could only contain a finite part of
$R_{T_{2}}$, in which case it would be impossible for $g$ to accommodate the
infinitely many triangles of $T^{\prime}_{1}$. This means that some copy
$C_{1}$ of $T_{1}$ in $T^{\prime}_{1}$ must be mapped by $g$ to the complement
of $R_{T_{2}}$ in $T^{\prime}_{2}$, and therefore to a copy $C_{2}$ of $T_{2}$
in $T^{\prime}_{2}$. Moreover, the edge $r_{i}v_{i}$ incident with $C_{1}$
must be mapped so that $g(r_{i})\leq g(v_{i})$ with respect to the tree order
$\leq$ of $C_{2}$ (extended to include the vertex of $R_{T_{2}}$ to which
$C_{2}$ attaches, which vertex serves as the root). This easily implies, by
induction of the layers of $C_{1}$, that $g$ embeds $C_{1}$ into $C_{2}$
preserving $\leq$. This proves our claim that $T_{1}<_{\leq}T_{2}$,
establishing (1).

∎

##  4 Universal elements for embeddable graphs

As mentioned in the introduction, C. Thomassen observed that for every closed
surface $\Sigma$ other than $\mathbb{S}^{2}$, the class of countable graphs
that embed in $\Sigma$ has no $<$-universal element. We repeat the argument
verbatim from [3, § 6]:

Indeed any such universal graph $U$ would contain a cycle $C$ whose deletion
reduces the Euler genus of $U$. Then every minor of $U$ can be embedded in a
simpler surface than $\Sigma$ after the deletion of at most $|C|$ vertices.
This however will not be the case for every graph embeddable in $\Sigma$.

Nevertheless, we will prove

######  Theorem 4.1.

Let $\Sigma$ be a closed orientable surface, and let $\mathcal{C}_{\Sigma}$ be
the class of countable graphs $G$ such that every component of $G\ $embeds in
$\Sigma$. Then $\mathcal{C}_{\Sigma}$ has a $<$-universal element.

The following will allow us to restrict our attention to locally finite graphs
in the proof of Theorem 4.1. Moreover, it allows us to choose our universal
graphs to be locally finite if we want to. A graph is _sub-cubic_ if it has
maximum degree 3.

######  Lemma 4.2.

Let $G$ be a countable graph embeddable in a closed surface $\Sigma$. There is
a sub-cubic graph $G^{\prime}$ embeddable in $\Sigma$ such that
$G<G^{\prime}$.

A proof of the special case of Lemma 4.2 where $\Sigma$ is the plane occupies
4 pages in [3]; our proof is simpler.111I suspect that it may be possible to
obtain a simpler construction of a universal planar graph by modifying the
construction of [6] so as to increase the number of subdivisions in each step.

The idea is to obtain $G^{\prime}$ by blowing up each vertex $v$ of $G\ $into
a locally finite tree $T_{v}$. For this to be possible we need enough space
around $v$ in order to embed $T_{v}$. This motivates the following definition.
An embedding $f:G\to\Sigma$ is called _generous around vertices_ , if for
every $v\in V(G)$ there is a topological open disc $D_{v}\subset\Sigma$ such
that $D_{v}\cap f(V(G))=f(v)$ and $D_{v}$ avoids $f(uw)$ for every edge $uw$
with $u,w\neq v$. Similarly, we say that $f$ is _generous around edges_ , if
for every $e=uv\in E(G)$ there is a topological open disc $D_{e}\subset\Sigma$
such that $D_{e}\cap f(G)=f(e)\backslash\\{f(u),f(v)\\}$. We call $f$
_generous_ if it is generous around both vertices and edges.

######  Proposition 4.3.

If a countable graph $G\ $admits an embedding into a surface $\Sigma$, then it
admits a generous one.

###### Proof.

Let $f:G\to\Sigma$ be an arbitrary embedding, and let
$(H_{n})_{n\in\mathbb{N}}$ be a sequence of finite connected subgraphs
_exhausting_ $G$, i.e. $\bigcup_{{n\in\mathbb{N}}}H_{n}=G$. We define an
embedding $g:G\to\Sigma$ which is generous around vertices by inductively
making local alterations to the way $f$ embeds $H_{n}$. We start by letting
$g(H_{0})=f(H_{0})$. Since $H_{0}$ is finite, we can choose disjoint closed
discs $D^{\prime}_{v}$ around each $f(v),v\in v(H_{0})$, each intersecting
$f(H_{0})$ at a small star around $v$. Let $D_{v}$ be a disc strictly
contained in $D^{\prime}_{v}$. For $n=1,2,\ldots$, having chosen $g(H_{n-1})$
and such discs around each vertex of $H_{n-1}$, we proceed to embed $H_{n}$.
If $f$ embeds any vertices $w$ of $H_{n}-H_{n-1}$ inside some $D_{v}$, then we
modify the part of $f$ intersecting $D^{\prime}_{v}$ so as to push the image
of $w$ into the annulus $D^{\prime}_{v}\backslash D_{v}$. Some easy
topological details are hereby left to the reader. We treat unwanted images of
edges intersecting $D_{v}$ similarly. Finally, we pick discs $D_{w}$ around
the new vertices $w$, disjoint from each other and any previously chosen
$D_{v}$, and proceed to the next step. The limit embedding
$g:\bigcup_{n}H_{n}\to\Sigma$ is generous around vertices by definition.

Starting with $g$ instead of $f$, and with a similar approach that this time
fixes, for each edge $uv\in E(G)$, an open disc $D^{\prime}_{uv}$ containing
$g(uv)\backslash(D_{u}\cup D_{v})$, we transform $g$ into an embedding that is
also generous around edges. ∎

###### Proof of Lemma 4.2.

Let $g:G\to\Sigma$ be a generous embedding (around vertices), as provided by
Proposition 4.3, with corresponding discs $D_{v},v\in V(G)$. Easily, we can
assume that these discs are pairwise disjoint, by choosing sub-discs if
needed. We will obtain $G^{\prime}$ by blowing up each vertex $v\in V(G)$ into
a tree $T_{v}$, embedded inside $D_{v}$.

To make this precise, let $\mathbb{T}_{2}$ be the infinite binary tree with
root $r$, and attach a leaf $\ell_{w}$ to each vertex $w$ of $\mathbb{T}_{2}$
to obtain the tree $T$. Embed $T$ in the closed unit disc $\mathbb{D}$ so that
$\ell_{w}$ is embedded between the two edges of $w$ leading away from $r$
(Figure 2). Easily, we may map all the leaves $\ell_{w}$ of $T$ on the
boundary $\partial\mathbb{D}$. Denote this embedding by
$f_{T}:T\to\mathbb{D}$.

\begin{overpic}[width=130.08731pt]{figT} \put(47.0,41.0){$r$}
\put(47.0,95.5){$\ell_{r}$} \put(11.0,5.0){$\partial\mathbb{D}$}
\put(47.0,15.0){$\mathbb{D}$} \end{overpic} Figure 2: The first few layers of
the embedding of $T$ in the proof of Lemma 4.2. Dashed lines denote edges
leading to leaves.

We remark that the ordering of the leaves of $T$ as they appear along the
circle $\partial\mathbb{D}$ is of the same type as the ordering of the
rationals $\mathbb{Q}\cap[0,1]$ by $<$: between any two elements there is a
third one.

We construct the desired embedded locally finite graph $G^{\prime}$ as
follows. For every $v\in V(G)$, let $\mathaccent 28695{D}_{v}$ be a closed
topological disc strictly contained in $D_{v}$. Delete $g(G)\cap\mathaccent
28695{D}_{v}$, and embed a copy $T_{v}$ of $T$ into $\mathaccent 28695{D}_{v}$
by composing $f_{T}$ with an isomorphism from $\mathbb{D}$ to $\mathaccent
28695{D}_{v}$. Next, delete $g(G)\cap D_{v}\backslash\mathaccent
28695{D}_{v}$, and note that every edge $uv\in E(v)$ is now mapped by what
remains of $g$ to an arc $A^{1}_{u}$ from $g(u)$ to a point
$u^{\prime}\in\partial D_{v}$ plus possibly some arcs with both edpoints on
$\partial D_{v}$, which arcs we also discard. Let $u_{1},u_{2},\ldots$ be a
(potentially finite) enumeration of $N(v)$. For each $i=1,2,\ldots$, choose an
arc $A^{2}_{u_{i}}$ in $D_{v}\backslash\mathaccent 28695{D}_{v}$ joining
$u^{\prime}_{i}$ to the image of a leaf $\ell_{i}$ of $T_{v}$. Note that the
union of $A^{1}_{u_{i}}$ with $A^{2}_{u_{i}}$ and the image $A^{3}_{u_{i}}$ of
the $\ell_{i}$–$v$ edge is an arc $A_{u_{i}v}$ from $u_{i}$ to $v$, and we
think of this arc as a replacement for the $u_{i}v$ edge of $G$. Thus we want
to make the above choices so that the $A_{u_{i}v}$ do not intersect except
possibly at their endpoints. In particular, we need to choose pairwise
distinct leaves $\ell_{i}$. These choices are however easy to make greedily:
having chosen $A^{2}_{u_{j}},j<i$, we use the remark about the ordering of the
leaves of $T_{v}$ from the previous paragraph, to choose a yet unused leaf
$\ell_{i}$, and an $u^{\prime}_{i}$–$\ell_{i}$ arc $A^{2}_{u_{i}}$ in
$D_{v}\backslash\mathaccent 28695{D}_{v}$ that avoids $A^{2}_{u_{j}},j<i$.

Thus we have constructed a locally finite graph $G^{\prime}$ embedded into
$\Sigma$. By construction, if we contract each $T_{v}$ into a vertex, then we
obtain $G$, which proves that $G<G^{\prime}$ as claimed. Note that
$G^{\prime}$ has maximum degree 4 by construction, and it is easy to modify
$T$ and $G^{\prime}$ to reduce it to 3. ∎

For the proof of Theorem 4.1 we will also use the following classical result
of Youngs about cellular embeddings.

######  Theorem 4.4 ([31]).

Let $\Sigma$ be a closed orientable surface, and let $G$ be a finite graph
that embeds into $\Sigma$ but does not embed into a closed orientable surface
of smaller genus. Then for every embedding $f:G\to\Sigma$, each face of $f$ is
homeomorphic to an open disc.

###### Proof of Theorem 4.1.

The idea for constructing a universal graph $U_{\Sigma}$ for
$\mathcal{C}_{\Sigma}$ is to fix a universal planar graph $P$, consider all
possible finite graphs $G\ $embeddable in $\Sigma$, attach a portion of $P$
along each face boundary of $G\ $in each of the countably infinitely many
possible ways, and take the disjoint union of the graphs arising from each
possibility. Let us make this more precise.

Fix an embedding $f_{P}:P\to\mathbb{S}^{2}$ of a $<$-universal planar graph
$P$ as provided by Theorem 1.1. For every finite graph $G\ $embeddable into a
closed orientable surface of genus at most $\gamma(\Sigma)$, let
$\Sigma^{\prime}$ be such a surface of minimum genus, and fix an embedding
$f_{G}:G\to\Sigma^{\prime}$. For every cycle $C$ of $G\ $that bounds a face of
$f_{G}$, choose a cycle $C^{\prime}$ of $P$ with length $|C^{\prime}|\geq|C|$.
(Here, if a face $F$ of $f_{G}$ is not bounded by a cycle but by a closed walk
with repeated vertices, we ignore $F$.) Choose one of the two sides $R$ into
which $C^{\prime}$ separates $P$ in $f_{P}$ by the Jordan curve theorem, and
denote it by $P_{C}$; that is, $P_{C}:=f_{P}^{-1}(\overline{R})$. Form a minor
$P^{\prime}_{C}$ of $P_{C}$ by contracting some subarcs of $C^{\prime}$ so
that the resulting minor of $C^{\prime}$ is a cycle $C^{\prime\prime}$ with
$|C^{\prime\prime}|=|C|$. Then form an infinite graph $G^{\prime}$ as follows.
For each facial cycle $C$ of $G$ with respect to $f_{G}$, attach
$P^{\prime}_{C}$ onto $G$ by identifying $C$ with $C^{\prime\prime}$ using any
of the $2|C|$ possible automorphisms $i:C\to C^{\prime\prime}$ as the
attachment map.

Note that there are countably infinitely many graphs $G^{\prime}$ that arise
this way: there are $\omega$ ways to choose $C^{\prime}$ for each of the
finitely many facial cycles $C$ of $G$, after which there are finitely many
ways to contract $C^{\prime}$, and attach $P^{\prime}_{C}$ onto $G$. We claim
that each such $G^{\prime}$ is embeddable into $\Sigma^{\prime}$, and
therefore $\Sigma$. Indeed, each $P^{\prime}_{C}$ is planar and hence
embeddable into the face $F_{C}$ of $f_{G}$ bounded by $C$. Here, we can use
Theorem 4.4 for convenience, to deduce that $F_{C}$ is homeomorphic with
$\mathbb{R}^{2}$. By uniting $f_{G}$ with such embeddings of the
$P^{\prime}_{C}$ we obtain an embedding of $G^{\prime}$ into
$\Sigma^{\prime}$.

Let $U^{\prime}_{G}$ be the disjoint union of all these graphs $G^{\prime}$,
and let $U_{G}=\omega\cdot U^{\prime}_{G}$ be the disjoint union of $\omega$
copies of $U^{\prime}_{G}$. Finally, let $U_{\Sigma}$ be the disjoint union of
$U_{G}$ over all finite $G\ $embeddable into $\Sigma$. By the above claim, we
have $U_{\Sigma}\in\mathcal{C}_{\Sigma}$.

It remains to prove that the graph $U_{\Sigma}$ we just constructed is
$<$-universal for $\mathcal{C}_{\Sigma}$. For this, let
$Y\in\mathcal{C}_{\Sigma}$ be connected. Let $X$ be a locally finite connected
graph such that $Y<X$, which exists by Lemma 4.2. We need to show that
$X<U_{\Sigma}$.

Let $H$ be a finite subgraph of $X$ with $\gamma(H)=\gamma(X)$. Here, we used
the well-known fact that a countable graph $X$ embeds into a surface $S$ if
each of its finite subgraphs $H$ does, which can be proved along the lines of
Proposition 4.3. We can assume for convenience that $H$ is an induced subgraph
of $X$. Let $g:X\to\Sigma^{\prime}$ be an embedding into the closed orientable
surface of genus $\gamma(X)$. Note that $g$ induces an embedding
$g_{H}:H\to\Sigma^{\prime}$. By Theorem 4.4, every face $F$ of $g_{H}$ is
homeomorphic to an open disc. Therefore, the subgraph $X_{F}:=g^{-1}(F)$ of
$X$ embedded into $F$ is planar. We are hoping to find $X$ as one of the
possible copies of $G^{\prime}$ in our construction of $U_{G}$ above, but one
of the obstacles is that some such faces $F$ may not be bounded by a cycle,
meaning they have been ignored during the construction of $G^{\prime}$, which
may then fail to contain a copy of $X_{F}$.

To address this obstacle, we will _‘fatten’_ $X$ to obtain a graph
$X^{\otimes}$ embedded in $\Sigma^{\prime}$ with better-behaved faces. We
assume that $g$ is generous, which we can by Proposition 4.3, and let
$\\{D_{v}\mid v\in V(X)\\}$ and $\\{D_{e}\mid e\in E(X)\\}$ be collections of
discs witnessing the generosity of $g$. We may further assume that the $D_{e}$
are pairwise disjoint.

######  Definition 4.5.

Let $X^{\prime\prime}$ be the multigraph obtained from $X$ by adding two
parallel edges $e^{\prime},e^{\prime\prime}$ to each edge $e\in E(X)$. We can
extend $g$ to embed $e^{\prime},e^{\prime\prime}$ using the fact that the
former is generous around edges: we can embed $e^{\prime},e^{\prime\prime}$
into the disc $D_{e}$ so that the circle $e^{\prime}\cup e^{\prime\prime}$
separates $e$ from the rest of $X$. Then, for each $e$ of $X^{\prime\prime}$
with end-vertices $u,v$, subdivide $e$ into a path of length 3 by declaring
two interior points $e_{u},e_{v}$ of $e$ to be vertices, so that $g(e_{u})\in
D_{u}$ and $g(e_{u})\in D_{v}$. Finally, for each vertex $v$ of
$X^{\prime\prime}$, and each two edges $e,f$ incident with $v$ that appear
consecutively in $D_{v}$, add an edge between $e_{v}$ and $f_{v}$, and embed
it inside $D_{v}$. We embed these edges in such a way that they form a circle
$S_{v}$ separating $v$ from any other vertex of $X$. Let $X^{\otimes}$ denote
the resulting graph, and $g^{\prime}$ its embedding into $\Sigma^{\prime}$;
see Figure 3.

Note that $X$ is a minor of $X^{\otimes}$, obtained by contracting the edges
inside each $S_{v}$ to a point. Thus all we have to do now is to find
$X^{\otimes}$ as a minor of $U_{\Sigma}$.

Let $H^{\otimes}$ be the subgraph of $X^{\otimes}$ corresponding to $H$, that
is, the subgraph of $X^{\otimes}$ induced by $\\{v\cup S_{v}\mid v\in
V(H)\\}$. Note that $H^{\otimes}$ has three types of faces in $g^{\prime}$:
(i) triangles comprising one edge of an $S_{v}$ and two edges of $v$, (ii)
squares joining two $S_{v}$’s, and (iii) faces corresponding to some face of
$g$. Thus by construction, every face $F$ of $H^{\otimes}$ is now bounded by a
cycle $C_{F}$ of $H^{\otimes}$, in other words, the closure $\overline{F}$ is
homeomorphic with a closed disc of $\Sigma^{\prime}$. Let
$X_{F}:=g^{{}^{\prime}-1}(\overline{F})$ be the subgraph of $X^{\otimes}$
embedded in $\overline{F}$. Note that $X_{F}$ is connected, because both
$X^{\otimes}$ and $C_{F}$ are. Moreover, $X_{F}$ is planar since it is
embedded into the disc $\overline{F}$.

We claim that $X^{\otimes}<U_{\Sigma}$. Recall that $U_{\Sigma}$ contains
infinitely many graphs of the form $G^{\prime}$, where $G$ is any finite graph
embeddable into $\Sigma^{\prime}$, and set $G=H^{\otimes}$. Establishing the
above claim is slightly more complicated than observing that each $X_{F}$
above is a minor of $P$, because we attached certain minors of $P$ to $G$ to
construct $G^{\prime}$, rather than $P$ itself. Another convenient feature of
our construction of $X^{\otimes}$ is the following property:

every vertex $v$ of $C_{F}$ has exactly one incident edge inside $F$ (and two
other edges in $C_{F}$). (2)

Indeed, our $v$ lies on some $S_{v}$, and $F$ lies completely inside or
outside $S_{v}$. (In the former case $X_{F}$ is just the triangle bounding
$F$; it is the latter case that is interesting.)

Since $X_{F}$ is planar, there is a minor $\Delta$ of $P$ isomorphic to
$X_{F}$. By (2), each vertex $v$ of $C_{F}$ has degree at most 3 in $X_{F}$,
and so we may assume that the corresponding branch set $B_{v}$ of $\Delta$ is
a finite tree with exactly three leaves. Let $P_{v}$ be the subpath of this
tree joining its two leaves participating in the copy of $C_{F}$ in $\Delta$.
Then $\bigcup_{v\in V(C_{F})}P_{v}$ induces a cycle $C^{\prime}_{F}$ in $P$.
Note that $f_{P}(C^{\prime}_{F})$ separates $\mathbb{S}^{2}$ into two regions
by the Jordan curve theorem, and as $\Delta$ is connected, one of these
regions $A$ contains $f_{P}(\Delta)$, where $f_{P}$ denotes our fixed
embedding of $P$ from above. Recall that when we constructed $G^{\prime}$, we
attached a minor $P^{\prime}$ of $P$ onto each face boundary $C$ of $G$, and
notice that $f_{P}^{-1}(\overline{A})$ is a candidate for $P^{\prime}$.
Applying this argument to each face $F$ of $G$, we deduce that $X^{\otimes}$
is a minor of $U_{G}$, and hence of $U_{\Sigma}$ as claimed.

Thus we have shown that every connected $Y\in\mathcal{C}_{\Sigma}$ is a minor
of $U_{\Sigma}$. By repeating the argument on each component, recalling that
$U_{\Sigma}$ contains infinitely many isomorphic copies of each of its
components, we obtain the same conclusion for disconnected $Y$ as well. Thus
$U_{\Sigma}$ is a $<$-universal element of $\mathcal{C}_{\Sigma}$.

∎

Figure 3: A portion of $X$ (left), and the corresponding part of $X^{\otimes}$
(right).

######  Remark 1.

The reason why we restrict Theorem 4.1 to orientable $\Sigma$ is that Theorem
4.4 fails in the non-orientable case; see [21] for details.

Let $\Gamma$ denote the class of countable graphs embeddable in some closed
orientable surface. In other words, $\Gamma$ comprises the graphs of finite,
but unbounded, orientable genus. Imitating the proof of Theorem 1.2, we have

######  Proposition 4.6.

$\Gamma$ does not have a $<$-universal element.

###### Proof.

Suppose $U$ is a universal graph in $\Gamma$, and let
$U^{\prime}:=U\dot{\cup}K_{5}$. Notice that $U^{\prime}\in\Gamma$, and
therefore $U^{\prime}<U$. Let $K_{0}$ be a minor of $K_{5}$ that extends to a
minor of $U^{\prime}$ in $U$. Apply the same argument on $U\backslash K_{0}$,
and repeat, to find $K:=\omega\cdot K_{5}$ as a minor of $U$. But this is
impossible since $K\not\in\Gamma$, a contradiction proving that $U$ does not
exist. ∎

Let $\Gamma^{*}$ denote the class of countable graphs every component of which
lies in $\Gamma$. Then $\Gamma^{*}$ does have a $<$-universal element, namely
the disjoint union of all the universal graphs provided by Theorem 4.1, when
$\Sigma$ ranges over all closed orientable surfaces.

###  4.1 2-compexes

The proof of Lemma 4.2 is likely to be adaptable to higher dimensions, in
particular to embeddings of 2-complexes into $\mathbb{R}^{3}$. This may be
helpful in addressing the following:

######  Question 4.1.

Does the class of countable 2-complexes embeddable into $\mathbb{R}^{3}$ (or
$\mathbb{R}^{4}$) have a $<$-universal element?

Here, the notion of minor we refer to is that of Carmesin [1], who obtained a
characterisation of the finite 2-complexes embeddable into $\mathbb{R}^{3}$
reminiscent of Kuratowski’s theorem. The interested reader is advised to also
consult [8, Theorem 3.2].

The analogue of Question 4.1 can be asked for the sub-family of those
2-complexes embeddable into $\mathbb{R}^{3}$ without accumulation points of
vertices. It might be that a disjoint union of copies of the 3-dimensional
cubic lattice is a universal element, in analogy with Kühn’s result [15].

##  5 Interlude: every embedded graph has a 3-connected supergraph

In this section we introduce another way to ‘fatten’ an embedded graph similar
to $X^{\otimes}$ from Definition 4.5, but more convenient for the purposes of
the proof of Theorem 6.1 in the next section. The idea is to attach a sequence
of triangles along each facial walk (Figure 4). This is a very simple
construction when $X$ is e.g. a finite plane graph, and we now provide the
details showing that it can be carried out for locally finite $X$ embedded in
any surface. Formally, we define our new ‘fattening’ $F(X)$ as follows.

Figure 4: An example of a plane graph $G\ $(solid lines) and its ‘fattening’
$F(G)$ (dashed lines).

######  Definition 5.1.

Let $X$ be a locally finite graph and $g:X\to\Sigma$ a generous embedding into
some surface $\Sigma$, the generosity of which is witnessed by collections of
discs $\\{D_{v}\mid v\in V(X)\\}$ and $\\{D_{e}\mid e\in E(X)\\}$. We define a
super-graph $F(X)$ of $X$ embedded in $\Sigma$ as follows. For each edge
$e=uv\in E(X)$, we embed a square $Q_{e}$ with vertices $ut_{1}vt_{2}$ into
$D_{e}$, where $t_{1},t_{2}$ are new vertices. We embed $Q_{e}$ so that $e$
lies in its interior. Thus $D_{e}$ now contains two triangles
$T_{1}=ut_{1}v,T_{2}=ut_{2}v$ sharing $e$. We call $t_{i}$ the _tip_ of
$T_{i}$. Having done so for every $e=uv\in E(X)$, we introduce some further
edges between tips of adjacent $T_{i}$’s as follows. For every $v\in V(X)$,
and any two tips $t,s$ such that the edges $vt,vs$ are consecutive in our
embedding, we embed a $ts$ edge into $\Sigma$. We thereby make sure that the
image of $ts$ does not intersect any other edge, new or old. (To see that this
is possible, extend $D_{v}$ to a topological disc $D^{\prime}_{v}$ that
contains all tips adjacent to $v$, and embed each $ts$ inside
$D^{\prime}_{v}$.) Let $F(X)$ denote the resulting graph, and $g^{\prime}$ its
embedding into $\Sigma$; see Figure 4.

We remark that for each (finite or infinite) facial walk $W=\ldots
e_{0}e_{1}\ldots$ bounding a face $A$ of $X$ in $g$, there is a facial path of
$F(X)$ in $g^{\prime}$ obtained by replacing each $e_{i}$ by the tip of its
triangle embedded in $A$.

We make the following observation about $F(X)$ that may be of independent
interest. It simplifies and generalises a construction of [7] (Lemma 5.3).

######  Proposition 5.2.

Let $G\subset\Sigma$ be a connected locally finite graph embedded in any
surface. Then $F(G)$ is 3-connected.

We emphasize that $G\ $is simple; the result fails in the presence of either
loops or parallel edges. We allow $\Sigma$ to be non-orientable and non-
compact.

###### Proof.

For $v\in V(G)$, let $C_{v}$ denote the subgraph of $F(G)$ induced by the
neighbours of $v$. Note that $C_{v}$ has a hamilton cycle, obtained by
visiting the neighbours of $v$ in the order their edges are embedded around
$v$ in $\Sigma$. Thus the subgraph $G_{v}$ of $F(G)$ induced by
$C_{v}\cup\\{v\\}$ has a spanning _wheel_ , and in particular $G_{v}$ is
3-connected. ($G_{v}$ is isomorphic to a wheel when $v$ lies in no triangle of
$G$.)

For $e=vu\in E(G)$, the _closed neighbourhood_ $N_{e}:=G_{v}\cup G_{u}$ of $e$
contains the union of two wheels sharing at least 4 vertices (namely $u,v$,
and the two tips of $e$). Thus $G_{v}$ cannot be separated from $G_{u}$ by any
two vertices. Since $G\ $is connected, it follows that $G=\bigcup_{v\in
V(G)}G_{v}$ is 3-connected. ∎

##  6 A universal $K_{5}$-free (and $K_{3,3}$-free) graph

In this section we prove the most difficult theorem of this paper:

######  Theorem 6.1.

The class of countable graphs with no $K_{5}$ minor has a $<$-universal
element.

A classical theorem of Wagner [30] says that a finite graph $G\ $is
$K_{5}$-minor-free if and only if $G\ $can be built from planar graphs and the
_Wagner graph_ by repeated 3-clique sums, where the Wagner graph $W$ is the
one depicted in Figure 5.

Figure 5: The Wagner graph.

Křìž & Thomas [16] (Theorem 6.4 below) extended Wagner’s result to infinite
graphs. Our construction of a universal graph $U$ proving Theorem 4.1 will use
this decomposition: the idea is to construct $U$ by repeated 3-clique sums of
a universal planar graph $P$ and copies of $W$. However, this will not work if
we let $P$ be any universal planar graph. Suppose, for example, $H$ is a 3-sum
of two planar graphs $G_{1},G_{2}$, and $K\subset G_{1}\cap G_{2}$ is a common
triangle. Although we can find both $G_{1},G_{2}$ as minors of $P$, it might
be that $H$ is not a minor of any 3-sum of two copies of $P$, just because $P$
may have no triangles. Thus we need to modify $P$ to ensure that it does have
a triangle wherever one is needed. This may look hopeless at first sight, but
it turns out there is a surprisingly simple construction that achieves it
—although proving that it does requires some effort. Once we have constructed
$P$ carefully enough that any $H$ as above is a minor of some 3-sum of two
copies of $P$, it will not be hard to show that any $K_{5}$-minor-free graph
is a minor of a certain repeated 3-sum of infinitely many copies of $P$ and
$W$.

We start our construction of $P$ by letting $P_{0}$ be a universal planar
graph, e.g. the one of Diestel and Kühn [3]. By Lemma 4.2, we may assume that
$P_{0}$ is locally finite. Pick any embedding $f_{0}:P_{0}\to\mathbb{S}^{2}$,
and let $P=F(P_{0})$ be the corresponding fattening. Thus $P$ is a locally
finite universal planar graph with plenty of triangles. We think of $P$ as a
plane graph with an embedding $f_{P}$ induced by $f_{0}$ (in fact $P$ is
3-connected by Proposition 5.2, so its embedding is known to be essentially
unique [11, 7], but we will not use this fact). As mentioned above, we need
something stronger than the existence of triangles in $P$; we will need the
following property (3). A _minimal $K_{3}$ minor_ of a graph $P$ is a family
$\Delta$ of three disjoint (possibly trivial) paths $M_{1},M_{2},M_{3}\subset
P$, called the branch sets of $\Delta$, and three edges $e_{1},e_{2},e_{3}$
joining the $M_{i}$’s so that $\bigcup_{1\leq i\leq 3}(M_{i}\cup e_{i})$ is a
cycle $C(\Delta)$.

For every minimal $K_{3}$ minor $\Delta$ of $P_{0}$, and any of the two
regions $R$ into which $C(\Delta)$ separates $\mathbb{S}^{2}$, there is a
triangle $\Delta^{\prime}\subset P=F(P_{0})$ contained in $\overline{R}$, and
three disjoint paths $P_{i},1\leq i\leq 3$ joining each vertex of
$\Delta^{\prime}$ to a distinct brach set of $\Delta$ (Figure 6). (3)

\begin{overpic}[width=130.08731pt]{figD} \put(45.0,40.0){$P_{2}$}
\put(70.0,8.0){$P_{3}$} \put(65.0,53.0){$P_{1}$}
\put(63.0,30.0){$\Delta^{\prime}$} \put(31.0,2.0){$e_{1}$}
\put(94.0,37.0){$e_{3}$} \put(28.0,64.0){$e_{2}$} \end{overpic} Figure 6: A
minimal $K_{3}$ minor (exterior cycle) and the triangle $\Delta^{\prime}$
(bold lines) as in 3.

We emphasize that $\Delta^{\prime}$ is a subgraph of $P$, not just a $K_{3}$
minor. Before we prove (3), let us see how it helps. Recall our above example
$H$, namely a 3-sum of two planar graphs $G_{1},G_{2}$ along a common triangle
$K$. As a warm-up towards the proof of Theorem 6.1, we will show that $H$ is a
minor of a 3-sum of two copies $P_{1},P_{2}$ of $P$. To see this, let $H_{i}$
be a $G_{i}$ minor of $P_{i}$ for $i=1,2$. Let $K_{i}$ be the part of $H_{i}$
corresponding to $K$. Pick a subpath of each of the three branch sets of
$K_{i}$ to form a minimal $K_{3}$ minor $\Delta_{i}$ of $P_{i}$. Assume for
simplicity that $K$ bounds a face in any embedding of $G_{i}$ (this can be
achieved, because if $K$ separates $G_{1}$, then we can further decompose
$G_{1}$ as a 3-sum). Then we can choose the $\Delta_{i}$ so that one of the
two sides $R_{i}$ of $C(\Delta_{i})$ does not intersect the rest of $H_{i}$.
Apply (3) to each triple $\Delta_{i},P_{i},R_{i}$ to obtain two triangles
$\Delta_{i}^{\prime}\subset P_{i}$ and their corresponding paths
$P_{ij},i\in\\{1,2\\},j\in\\{1,2,3\\}$. Identify $\Delta_{1}^{\prime}$ with
$\Delta_{2}^{\prime}$ to obtain a 3-sum $Q$ of $P_{1},P_{2}$. (To picture
this, imagine a copy of Figure 6 as a substructure of each $P_{i}$, with the
two copies of $\Delta^{\prime}$ glued together.) Extend $H_{1}$ by attaching
one of the $P_{1j}$ to each of the three branch sets of $K_{1}$. Do the same
for $H_{2}$. By uniting $H_{1}$ with $H_{2}$ we thus find a minor of $Q$
isomorphic to $H$.

###### Proof of (3).

Given a cycle $C$ of a plane graph $G$, and one of the sides $A$ into which
$C$ separates the plane, we say that $C$ is _induced inside $A$_, if no chord
of $C$ lies in $A$.

Let us first consider the case where $C=C(\Delta)$ is induced inside $R$. Let
$B$ be one of the branch sets of $\Delta$ —hence $B$ is a sub-path of $C$— and
let $e=uv$ be the edge of $C$ joining the other two branch sets of $\Delta$
(Figure 7). Let $t$ be the tip of $e$ inside $R$. The desired triangle
$\Delta^{\prime}$ is $uvt$. Two of the desired paths $P_{1},P_{2}$ are the
singletons $\\{u\\}$ and $\\{v\\}$, and so it remains to find a $t$–$B$ path
$P_{3}$ in $R$ avoiding $u,v$. For this, pick a vertex $x$ in $B$, let $Q$ be
one of the two $x$–$e$ paths in $C$ and let $t^{\prime}$ be the tip of the
first edge of $Q$. Recall from Proposition 5.2 that the closed neighbourhood
$G_{w}$ of every $w\in V(P_{0})$ has a spanning wheel, and note that
$G_{w}\cap R$ contains a path $Q_{w}$ joining the tips of the two edges of $w$
in $C$. By concatenating the $Q_{w}$ as $w$ moves along $Q$ we obtain a
$t$–$t^{\prime}$ path in $R$, and by appending the edge $t^{\prime}x$ we
obtain the desired $t$–$x$ path $P_{3}$.

\begin{overpic}[width=238.49231pt]{figQ} \put(1.0,30.0){$B$}
\put(35.0,17.0){$P_{3}$} \put(94.0,14.0){$v$} \put(95.0,34.0){$u$}
\put(81.0,26.0){$t$} \put(22.0,22.0){$t^{\prime}$} \put(5.0,21.0){$x$}
\put(50.0,0.0){$Q$} \end{overpic} Figure 7: Finding $P_{3}$ in the proof of
(3).

It remains to handle the general case where $C=C(\Delta)$ is not induced
inside $R$, but it is possible to reduce it to the induced case as follows.
Given a plane graph $G$, a minimal $K_{3}$ minor $\Delta_{0}$ of $G$, one of
the two regions $A$ into which $C(\Delta_{0})$ separates $\mathbb{S}^{2}$, and
a chord $h$ of $C(\Delta_{0})$ in $A$, we can use $h$ as a shortcut of
$\Delta$ to replace it by a minimal $K_{3}$ minor $\Delta_{1}$ of $G$ inside
$A$ each branch set of which is contained in a distinct branch set of
$\Delta_{0}$, and at least one of these containments is proper. We repeat as
long as possible, ending up with a $\Delta_{k}$ which is induced inside a
subregion $R$ of $A$. Thus replacing $\Delta$ with $\Delta_{k}$ we can reduce
to the induced case handled above. Note that each branch set of $\Delta_{k}$
is contained in a distinct branch set of $\Delta=\Delta_{0}$ by induction, and
so the $P_{i}$’s we obtain do reach $\Delta$. ∎

Our universal graph will be constructed so that it comes with a tree
decomposition into parts each of which is a copy of either $P$ or the Wagner
graph $W$. Let us recall the relevant definitions.

A _tree decomposition_ of a graph $G$ is a pair $(T,X)$, where $T$ is a tree
and $X=\\{X^{t}\mid t\in V(T)\\}$ is a family of subgraphs of $G$, called
_torsos_ , such that

  * (T1)

$\bigcup_{t\in V(T)}X^{t}=V(G)$,

  * (T2)

every edge $e$ of $G$ lies in some $X^{t}$, and

  * (T3)

if $t,s,q\in V(T)$ and $s$ is on the path between $s$ and $q$, then $X^{t}\cap
X^{q}\subseteq X^{s}$.

We say that a tree-decomposition $(T,X)$ is a _$k$ -decomposition_ of $G$ over
a graph class $\Gamma$, if

  * (T4)

$|V(X^{t}\cap X^{s})|\leq k$ for every ${ts}\in E(T)$, and,

letting $G^{*}$ be the graph obtained from $G$ by joining every edge which has
both its endpoints in some $X^{t}\cap X^{s}$ for some ${ts}\in E(T)$,

  * (T5)

$G^{*}\upharpoonright V(X^{t})\in\Gamma$ for every $t\in V(T)$.

Let $G,G^{\prime}$ be two graphs, and let $K\subseteq G,K^{\prime}\subseteq
G^{\prime}$ be cliques of equal size. A _clique-sum_ of $G,G^{\prime}$ is a
graph $H$ obtained from their disjoint union by identifying $K$ with
$K^{\prime}$ via a bijection of their vertices, and then possibly deleting any
of the edges of the resulting clique $K=K^{\prime}$ of $H$. A _$k$ -clique-
sum_, or just _$k$ -sum_, is a clique-sum in which these cliques have at most
$k$ vertices.

A graph $G\ $is called a _$k$ -simplex_ if it does not contain a $k$-cut, i.e.
a clique on at most $k$ vertices the removal of which disconnects $G$.

Let $\Gamma$ denote the class of countable graphs that are either planar or
isomorphic to $W$.

Our universal graph $U$ will come with a $3$-decomposition $(S,Y)$ over
$\Gamma$, where $S$ is the regular tree of degree $\omega$, and each $Y^{t}$
is isomorphic to either $P$ or $W$. We will define $U$ in such a way that
makes it maximal with these properties in the sense that any other such graph
is a subgraph of our $U$, although we will not formally state or use this
maximality property.

Our construction of $U$ follows the lines of Mohar’s tree amalgamation [19],
but with certain differences that make it more restricted in some sense and
more general in another. The idea is to keep forming 3-sums of infinitely many
copies of $P$ and $W$ in all possible ways. Our formal definition of $U$ is as
follows.

######  Definition 6.2.

Let $S$ be a tree every vertex of which has countably infinite degree (this
fixes $S$ up to isomorphism). Let $k$ be a colouring of $V(S)$ by two colours,
red and blue say, such that every vertex has infinitely many neighbours of
each colour. For each $v\in V(S)$, we let $Y^{v}$ be a copy of $P$ if $k(v)$
is blue, and a copy of $W$ if $k(v)$ is red. Moreover, we label each directed
edge $uv$ of $S$ by an isomorphism $c_{uv}$ from some clique $K$ of $Y^{u}$
with at most 3 vertices to a clique of $Y^{v}$. Thus $K$ is a triangle, edge,
or vertex, and if $Y^{u}$ or $Y^{v}$ is a copy of $W$, it must be an edge or
vertex. We choose the labelling $c$ in such a way that for every $u\in V(S)$,
every clique $K$ of $Y^{u}$ with at most 3 vertices, and every isomorphism $h$
from $K$ to a subgraph of $P$ or $W$, there are infinitely many outgoing edges
$uv$ such that $c_{uv}=h$ (whereby $v$ is blue if $h(K)$ is a subgraph of $P$,
and red otherwise). It is easy to construct such a labelling greedily,
starting from a ‘root’ vertex of $S$.

To define $U$, we take the disjoint union of $\\{Y^{v}\mid v\in V(T)\\}$, and
then for every directed edge $uv$ of $S$, we identify each vertex $x$ in the
domain of $c_{uv}$ with $c_{uv}(x)$.

This completes the construction of $U$. Clearly, $(S,Y)$ is a 3-decomposition
of $U$. To establish Theorem 6.1 it now remains to prove

######  Proposition 6.3.

For every countable graph $G\ $with no $K_{5}$ minor, $G<U$ holds.

Before proving this, we state the aforementioned result of Křìž & Thomas.

######  Theorem 6.4 ([16, Theorems 3.5 and 3.9]).

A countable graph $G\ $is $K_{5}$-minor-free if and only if $G\ $has a
supergraph $G^{*}$ which has a tree decomposition $(T,X)$ such that

  1. (A)

$G[X^{t}]$ is a 3-simplex in $\Gamma$ for every $t\in V(T)$, and

  2. (B)

$X^{s}\cap X^{t}$ is a clique on at most 3 vertices for every $s,t\in V(T)$.

######  Remark 2.

Theorem 6.4 is not formulated in [16] exactly as stated here, so let me
explain how our formulation follows from the results of [16]. A _3-complex_
over $\Gamma$ is a graph $G\ $such that every 3-simplex contained in $G\
$belongs to $\Gamma$. By [16, Theorem 3.9], if every finite subgraph of $G\
$is a subgraph of a 3-complex over $\Gamma$ —which is the case by Wagner’s
aforementioned theorem— then so is $G$. Implication $(ii)\to(iii)$ of [16,
Theorem 3.5] then says that $G$ admits a tree decomposition $(T,X)$ over
$\Gamma$ with adhesion sets of size at most 3 (condition (T4)), and that after
making $X^{s}\cap X^{t}$ complete both $X^{s},X^{t}$ remain in $\Gamma$
(condition (T5)). We let $G^{*}$ be the graph obtained from $G\ $after making
each adhesion set of $(T,X)$ complete, and so (B) is satisfied. Condition (A)
is satisfied too by the construction of $(T,X)$: each $X^{t}$ is induced by a
maximal clique of an auxiliary graph $H^{*}$, and condition $(*)$ of [16] says
that it is a 3-simplex of $G$.

###### Proof of Proposition 6.3.

Apply Theorem 6.4 to obtain the tree decomposition $(T,X)$. We may assume
without loss of generality that $G=G^{*}$, because the latter is
$K_{5}$-minor-free too as a consequence of this decomposition. In particular,
we may assume that $G\ $is connected.

Let $(t_{n})_{n\in\mathbb{N}}$ be an enumeration of $V(T)$ such that
$T[\\{t_{0},\ldots,t_{k}\\}]$ is connected for every $k\in\mathbb{N}$. We will
inductively embed each $X_{i}:=X^{t_{i}}$ as a minor $H_{i}$ of some torso
$Y_{i}=Y^{s_{i}}$ of the above tree decomposition $(S,Y)$ of $U$, using 3 to
ensure that adhesion sets are embedded as common sub-minors. The branch sets
of each $H_{i}$ will be either fixed or enlarged in subsequent steps, and so
we will obtain a minor of $G\ $in $U$ in the limit $i\to\infty$.

The first step $i=0$ is easy: pick a torso $Y_{0}$ of $(S,Y)$ which is
isomorphic to $W$ if $X_{0}$ is, and isomorphic to $P$ if $X_{0}$ is planar.
Let $H_{0}$ be a minor of $Y_{0}$ isomorphic to $X_{0}$; in the former case
this is trivial, and in the latter it is possible because $P_{0}$ is a
universal planar graph. We insist that $H_{0}$ be a minor of the $P_{0}$
subgraph of $Y_{0}$ in this case, i.e. $H_{0}$ uses no tips of $P=F(P_{0})$.

For the inductive step, assume that step $i-1$ concluded with a minor of
$\bigcup_{k<i}X_{k}$ in $U$, contained in the union of finitely many torsos of
$(S,Y)$, whereby we have defined a minor $H_{k}$ of some $Y_{k}$ isomorphic to
$X_{k}$ for every $k<i$. Let $t^{j}$ be the unique neighbour of $t^{i}$ in $T$
such that $j<i$, the existence and uniqueness of which is guaranteed by the
choice of $(t_{n})_{n\in\mathbb{N}}$. As above, we will choose a torso
$Y_{i}=Y^{s_{i}}$ of $(S,Y)$ which is isomorphic to $W$ if $X_{i}$ is, and
isomorphic to $P$ if $X_{i}$ is planar, and we will find a minor $H_{i}$ of
$Y_{i}$ isomorphic to $X_{i}$. But this time we have to make our choices
carefully.

We first consider the case where $X_{i}$ is planar, and $X_{i}\cap X_{j}$ is a
triangle $\Delta^{o}$. This case will be handled almost identically with the
warm-up following (3). Let $H_{i}$ be a minor of $P_{0}\subset P$ isomorphic
to $X_{i}$. Let $\Delta$ be the triangle of $H_{i}$ corresponding to
$\Delta^{o}$. Recall that $X_{i}$ is a 3-simplex by (A), and therefore
$\Delta^{o}$ is facial in any embedding of $X_{i}$ into $\mathbb{S}^{2}$. This
implies that one of the regions $R$ into which $H_{i}$ separates
$\mathbb{S}^{2}$ in our fixed embedding $f_{P}:P\to\mathbb{S}^{2}$ is bounded
by $\Delta$ and meets no other branch sets or branch-edges of $H_{i}$. Thus,
after choosing a subpath of each branch set of $\Delta$ to turn it into a
minimal $K_{3}$ minor of $P$, we can apply (3) to $\Delta$ and $R$ to obtain a
triangle $\Delta^{\prime}_{i}\subset P$ and disjoint paths $P_{i},1\leq i\leq
3$ joining its vertices to distinct brach sets of $\Delta$. Note that the
$P_{i}$ are disjoint from any branch set and edge of $H_{i}$ not contained in
$\Delta$, because they lie in $R$. We modify $H_{i}$ by enlarging each branch
set of $\Delta$ by uniting it with its unique incident $P_{i}$. Now $H_{i}$ is
still isomorphic to $X_{i}$, and each branch set of $\Delta$ contains a unique
vertex of $\Delta^{\prime}$.

Notice that in this case, i.e. when $X_{i}\cap X_{j}$ is a triangle, $X_{j}$
is planar too because $W$ has no triangles. Thus in step $j$, we defined an
$X_{j}$ minor $H_{j}$ of some $Y_{j}\cong P$. By repeating the above arguments
with $X_{i}$ replaced by $X_{j}$, we can find a triangle
$\Delta^{\prime}_{ji}\subset Y_{j}$, and enlarge the branch sets of a triangle
$\Delta_{ji}$ of $H_{j}$ if needed, to ensure that they each contain exactly
one vertex of $\Delta^{\prime}_{ji}$. Note that it might be that
$\Delta_{ji}=\Delta_{jk}$ for some $k<i$, in which case we choose
$\Delta^{\prime}_{ji}=\Delta^{\prime}_{jk}$, and do not enlarge any branch
sets.

We choose $Y_{i}$ to be a neighbour of $Y_{j}$ in $S$ —more precisely, $s_{i}$
is a neighbour of $s_{j}$— that has not been chosen as $Y_{k}$ in any of the
previous steps $k$. There are infinitely many such $Y_{i}$ to choose from by
the construction of $U$. In addition, we make this choice so that the
attachment map dictated by the label $c(s^{j}s^{i})$ attaches $Y_{j}$ to
$Y_{i}$ by identifying $\Delta^{\prime}$ with $\Delta^{\prime}_{ji}$ so that
two vertices get identified whenever they correspond to the same vertex of
$\Delta^{o}$. Then, for each vertex $v$ of $\Delta^{o}$, we unite the
corresponding branch sets $B_{v}^{j},B_{v}^{i}$ of $H_{j}$ and $H_{i}$ into
one branch set $B$, noting that $B$ is connected because $B_{v}^{j},B_{v}^{i}$
contain a common vertex in $\Delta^{\prime}_{ji}$. We have thus extended our
minor of $\bigcup_{k<i}X_{k}$ in $U$ inherited from step $i-1$ into a minor of
$\bigcup_{k\leq i}X_{k}$. This concludes step $i$ in the case where $X_{i}$ is
planar, and $X_{i}\cap X_{j}$ is a triangle.

The other cases are simpler. If $X_{i}$ is planar, and $X_{i}\cap X_{j}$ is an
edge $e=uv\in E(G)$, then let again $H_{i}$ be a minor of $P_{0}\subset P$
isomorphic to $X_{i}$. Let $B^{i}_{u},B^{i}_{v}$ be the branch sets of
$H_{i}$, corresponding to $u$ and $v$, and pick a $B^{i}_{u}$–$B^{i}_{v}$ edge
$e^{i}$ in $P$. Likewise, we let $B^{j}_{u},B^{j}_{v}$ be the corresponding
branch sets of $H_{j}$, and pick an edge $e^{j}$ joining them in $Y_{j}$, but
if a $B^{j}_{u}$–$B^{j}_{v}$ edge $e^{k}$ was chosen in some previous step $k$
(because some $X_{k}$ also attaches to $X_{j}$ along $e^{k}$), then we let
$e^{j}=e^{k}$. As above, pick an isomorphism $\iota^{i}:X_{i}\to P$, and
choose $Y_{i}$ to be a neighbour of $Y_{j}$ in $S$ that has not been chosen as
$Y_{k}$ in any of the previous steps $k$, and attaches to $Y_{j}$ by
identifying $e^{i}$ with $e^{j}$ in the direction dictated by $\iota^{i}$. For
each end-vertex $x$ of $e$, we unite $B^{j}_{x}$ and $B^{i}_{x}$ into one set,
which set we declare to be our $i$th branch set of $x$.

If $X_{i}$ is a copy of $W$, and $X_{i}\cap X_{j}$ is an edge, we proceed as
in the previous case, with the obvious difference being that we choose $Y_{i}$
to be a copy of $W$ instead of $P$.

Finally, if $X_{i}\cap X_{j}$ is a vertex $v\in V(G)$, then our task becomes
easier. We proceed as above, and ensure that $Y_{i}$ attaches to $Y_{j}$ so
that the branch sets corresponding to $v$ in $H_{i}$ and $H_{j}$ contain the
unique common vertex of $Y_{i},Y_{j}$, and we unite these two branch sets into
one.

Note that at each step $i$ we have associated to each $v\in V(\bigcup_{k\leq
i}X_{k})$ a disjoint branch set $B_{v}^{i}\subset U$, so that if $vu\in
E(\bigcup_{k\leq i}X_{k})$ then there is a $B_{v}^{i}$–$B_{u}^{i}$ edge in
$U$. Moreover, $B_{v}^{i}$ is increasing with $i$. Thus the family of branch
sets $\\{\bigcup_{i\in\mathbb{N}}B_{v}^{i}\mid v\in V(G)\\}$ defines a $G$
minor in $U$. ∎

Similarly to Theorem 6.4, Křìž & Thomas [16] extended another result of
Wagner, saying that the $K_{3,3}$-minor-free graphs are exactly the 2-clique-
sums of planar graphs and $K_{5}$. By imitating the proof of Theorem 6.1 we
can thus deduce

######  Theorem 6.5.

The class of countable graphs with no $K_{3,3}$ minor has a $<$-universal
element.

A universal element can be obtained as in Definition 6.2, except that we
replace $W$ by $K_{5}$, and do not allow $K$ to be a triangle. (We may use
$P_{0}$ instead of $P$ this time.)

###  6.1 Bounding the maximum degree

Recall that every graph $G\ $embeddable in a surface $\Sigma$ is a minor of a
graph $H$ of maximum degree $\Delta(H)=3$ that also embeds in $\Sigma$. This
property is not enjoyed by all minor-closed classes even if we increase the
$\Delta(H)$ we allow. The class of stars $\mathrm{Forb}(P_{3})$ is an easy
example, and one can prove that apex graphs provide another example.

######  Definition 6.6.

Given a minor-closed graph family $\mathcal{C}$, define $\Delta(\mathcal{C})$
as the smallest cardinal $k$ such that for every $G\in\mathcal{C}$ there is
$H\in\mathcal{C}$ with $\Delta(H)\leq k$ and $G<H$.

As mentioned above, $\Delta(\mathcal{C})$ can be infinite. I am not aware of
any studies of this parameter even for finite graphs. For which minor-closed
classes $\mathcal{C}$ of finite graphs is $\Delta(\mathcal{C})$ finite? This
question is perhaps too general to admit a concrete answer, but here is a more
specific problem that I find interesting:

######  Conjecture 6.1.

Every proper minor-closed class of countable graphs is contained in such a
class $\mathcal{C}$ with finite $\Delta(\mathcal{C})$.

_Proper_ here means that $\mathcal{C}$ does not contain all countable graphs.

Perhaps the finiteness of $\Delta(\mathcal{C})$ can be used to formalise the
idea that we do not need apex vertices to describe the graphs in $\mathcal{C}$
in structure theorems in the spirit of Robertson & Seymour [25].

In the rest of this section we prove that $\Delta(\mathcal{C})$ is finite for
the $K_{5}$-minor-free and $K_{3,3}$-minor-free graphs.

######  Proposition 6.7.

The universal $K_{5}$-minor-free graph of Theorem 6.1 can be chosen to have
maximum degree 22.

###### Proof.

We will alter the construction of $U$ in Definition 6.2 so as to never glue
two copies of $P$ or $W$ directly; instead, we expand $P$ and $W$ by adding
new cliques that we use to form 3-sums without increasing vertex degrees too
much.

Let us make this precise. A _$k$ -pilar_ is a graph of the form $K_{k}\times
R$ where $\times$ stands for the cartesian product, and $R$ is a ray. Its
_base_ is the subgraph $K_{k}\times\\{r\\}$ where $r$ is the first vertex of
$R$.

Let $P^{\square}$ be the graph obtained from $P$ by introducing a $k$-pilar
$R_{K}$ for every clique $K$ of $P$ of size at most $3$, identifying the base
of $R_{K}$ with $K$.

Recall that $P$ was defined as $F(P_{0})$, where $P_{0}$ is any universal
planar graph. By Lemma 4.2, we may assume $\Delta(P_{0})=3$. This implies that
$\Delta(P)=9$ by the construction of $F(P_{0})$. Moreover, by subdividing each
edge of $P_{0}$ if needed, we may assume that $P_{0}$ has no $K_{3}$ subgraph.
We claim that

$\Delta(P^{\square})\leq 28$. (4)

Indeed, each pilar we attach to a vertex $v$ of $P$ increases its degree by 1.
Note that $v$ is incident with exactly one $1$-pilar of $P^{\square}$, and at
most $d(v)\leq 9$ $2$-pilars. Let us bound the number $3$-pilars. Since
$P_{0}$ has no $K_{3}$ subgraph, the closed neighbourhood of $v$ in $P$ is
isomorphic to a wheel by construction (recall Proposition 5.2), and therefore
$v$ lies in exactly 9 triangles of $P$. Thus $v$ is incident with at most nine
$3$-pilars. This gives $d_{P^{\square}}(v)\leq 9+1+9+9=28$ as claimed.

We define $W^{\square}$ similarly to $P^{\square}$, starting with $W$ instead
of $P$. Easily, $\Delta(W^{\square})<28$.

We change the construction of $U$ in Definition 6.2 in two ways. Firstly,
instead of letting each torso $Y_{i}$ of $S$ to be a copy of $P$ or $W$, we
use $P^{\square}$ or $W^{\square}$. Secondly, whenever we previously attached
a clique $K$ of $Y_{i}$ to a clique $K^{\prime}$ of $Y_{j}$, we now attach a
copy of $K$ from its pilar to a copy from the pilar of $K^{\prime}$, whereby
we do not allow any of these copies to be the base of the pilar. There are
infinitely many copies to choose from, and we make those choice in such a way
that each copy is only used once. This can easily be achieved e.g. by using a
bijection between $V(S)\times V(S)$ and the vertices of the ray $R$ used in
the definition of the pilars. The resulting graph $U^{\square}$ thus satisfies
$\Delta(U^{\square})\leq 28$ by construction, the bottleneck being (4).

It remains to check that $U^{\square}$ is $K_{5}$-minor-free universal, and
this is true because $U<U^{\square}$. Indeed, by contracting each copy of $R$
in each pilar of our construction we obtain $U$ as a minor of $U^{\square}$.

In fact, a closer inspection of the proof of Proposition 6.3 reveals that we
can save a little. It suffices to only form 2-sums of original edges of
$P_{0}\subset P$ in the construction of $U$. Thus we only need to attach
2-pilars to those edges, saving a factor of 6. ∎

A universal $K_{3,3}$ graph with bounded maximum degree can be constructing
along the same lines. Since we do not need 3-sums in this case, we can define
$U^{\square}$ starting with $P=P_{0}$, and only attaching 1- and 2-pilars. The
resulting upper bound on the degrees of $U^{\square}$ is $4+1+4=9$, the
bottleneck being $K_{5}^{\square}$ rather than $P^{\square}$.

Thus we have proved Corollary 1.7.

######  Question 6.2.

What are the optimal upper bounds on the maximum degree in Corollary 1.7?

##  7 Further remarks and questions

###  7.1 Forbidding some finite graph componentwise

Diestel & Kühn [3] asked whether $Forb(K_{n})$ has a $<$-universal element.
The cases $5<n<\infty$ remain open, and our proof of Theorem 6.1 suggests that
they may be hard to answer. Let us suppose that $Forb(K_{n})$ has a
$<$-universal element $F_{n}$ for every $n$. Then
$\bigcup_{n\in\mathbb{N}}F_{n}$ would be universal for the class $\mathcal{F}$
of graphs $G\ $such that no component of $G\ $contains all finite graphs as
minors. It would be interesting to try to prove this directly:

######  Conjecture 7.1.

The class $\mathcal{F}$ has a $<$-universal element.

It is not hard to prove that $\mathcal{F}=\mathrm{Forb}(X)$ where $X$ is the
graph obtained from $\\{K_{n}\mid{n\in\mathbb{N}}\\}$ by picking one vertex
from each $K_{n}$ and identifying them.

To prove Conjecture 7.1 it would suffice to find a sequence
$(\mathcal{C}_{n})_{n\in\mathbb{N}}$ of minor-closed classes with
$<$-universal elements $U_{n}$ such that every finite graph belongs to some
$\mathcal{C}_{n}$ using the above idea. Candidates for such sequences can be
sought among geometrically defined classes of graphs. One example is letting
$\mathcal{C}_{n}$ be the class of graphs of ‘dimension’ $d=n$, where $d$ is
e.g. the Colin de Verdière invariant or the paremeter $\sigma$ of van der
Holst & Pendavingh [29]. As a first (or rather second) step in this direction
one can ask

######  Question 7.2.

Do the countable linklessly-embeddable graphs have a $<$-universal element?

For the definition of linklessly-embeddable graphs, and alternative
characterizations of this family, we refer to [24]. I expect that these
characterizations remain equivalent in the infinite case.

Another approach for attacking Conjecture 7.1 would be to try to employ the
Graph Structure Theorem of Robertson & Seymour [25]. This raises the following
question, for which our results of Section 6 provide support:

######  Problem 7.3.

Are the families with $<$-universal elements closed under $k$-sums for every
$k$?

We remark that if $\mathcal{C}$ has a $<$-universal element $U$, then
$\mathrm{Apex(\mathcal{C})}$, i.e. the class of cones over graphs in
$\mathcal{C}$, has the cone over $U$ as a universal element.

###  7.2 Co-finite graphs

We say that a minor-closed graph class $\mathcal{C}$ is _co-finite_ , if
$\mathcal{C}=\mathrm{Forb}(S)$ for a set $S$ of finite graphs (which can be
chosen to be finite by the Robertson–Seymour theorem [26]). Note that a graph
$G\ $belongs to such a class $\mathcal{C}$ if and only if every finite minor
of $G\ $does. Call an infinite graph $G\ $_co-finite_ , if
$\mathcal{C}_{G}:=\\{H\mid H<G\\}$ is co-finite.

It follows from the definitions that

######  Observation 7.1.

A countable graph $G$ is co-finite if and only if $G$ is a $<$-universal
element of a co-finite minor-closed class $\mathcal{C}$ (with
$\mathcal{C}=\mathcal{C}_{G}$).∎

By the Graph Minor Theorem [26], there are at most countably many countable
co-finite graphs. Let us show that there are infinitely many. The regular tree
$G_{0}$ of countably infinite degree is a $<$-universal element of the class
of forests $\mathcal{C}_{0}=\mathrm{Forb}(K_{3})$. It follows that for every
${n\in\mathbb{N}}$, the graph $G_{n}$ obtained from $G_{0}$ by adding $n$ new
vertices and connecting them completely will all other vertices is universal
for the $n$-apex forests. Another infinite family can be obtained similarly,
starting with $G_{0}$ being a universal planar graph.

These examples combined with the discussion of Section 6.1 motivate

######  Question 7.4.

Is there an infinite set of locally finite co-finite graphs no two of which
are minor-twins?

A famous problem of Thomas [28] asks whether the countable graphs are well-
quasi-ordered under $<$. The restriction to co-finite graphs may be more
accessible:

######  Problem 7.5.

Are the countable co-finite graphs well-quasi-ordered under $<$?

###  7.3 Addable classes

Recall from the introduction that the class $\mathcal{E}_{\Sigma}$ of
countable graphs that embed in a closed surface
$\Sigma\not\cong\mathbb{S}^{2}$ has no $<$-universal element, but the class
$\mathcal{E}_{\Sigma}^{*}$ of graphs with components in $\mathcal{E}_{\Sigma}$
does. This section attempts to use these facts as a lesson to come up with a
more concrete version of Question 1.1.

A graph class $\mathcal{C}$ is called _addable_ , if $G,H\in\mathcal{C}$
implies $G\dot{\cup}H\in\mathcal{C}$. We say that $\mathcal{C}$ is _$\sigma$
-addable_, if $G_{n}\in\mathcal{C}$ for ${n\in\mathbb{N}}$ implies
$\dot{\bigcup}_{{n\in\mathbb{N}}}G_{n}\in\mathcal{C}$.

######  Proposition 7.2.

A co-finite minor-closed graph class $\mathcal{C}$ is addable if and only if
each $F\in\mathrm{Ex}(\mathcal{C})$ is connected. An arbitrary minor-closed
graph class $\mathcal{C}$’ satisfying
$\mathcal{C}=\mathrm{Forb}(\mathrm{Ex}(\mathcal{C}^{\prime}))$222See Section
2.3 to recall how this could fail. is $\sigma$-addable if and only if each
$F\in\mathrm{Ex}(\mathcal{C}^{\prime})$ (is connected or) has a connected
minor-twin. ∎

Variants of this for finite graphs are well-known. The proof is an exercise
that we leave to the reader. To see that the restriction to co-finite classes
is essential in the first statement, consider the class $\mathcal{C}$ of
graphs embeddable in any closed surface. This $\mathcal{C}$ is addable (but
not $\sigma$-addable), but $\mathrm{Ex}(\mathcal{C})$ contains $\omega\cdot
K_{5}$, which has no connected minor-twin. As another example, let
$\mathcal{U}$ be the class of graphs with at most one cycle. It is easy to see
that $\mathcal{U}$ has no $<$-universal element, and that it is not addable.
But $\mathcal{U}^{*}$ has one: a disjoint union of cycles of all possible
lengths, with copies of the $\omega$-regular tree attached to each of their
vertices.

Motivated by the above discussion, and Corollary 1.3, we propose

######  Problem 7.6.

Let $F_{1},\ldots,F_{k}$ be finite connected graphs. Must
$\mathrm{Forb}(F_{1},\ldots,F_{k})$ have a $<$-universal element?

In other words, the question is whether every co-finite, addable, minor-closed
class has a $<$-universal element.

We remark that the co-finite classes of countable graphs are in one-to-one
correspondence with classes of finite graphs. Our final problem emphasizes the
idea that some questions about infinite universal graphs can be thought of as
questions about finite graphs:

######  Problem 7.7.

Let $F_{1},\ldots,F_{k}$ be finite graphs. Is the problem of deciding whether
$\mathrm{Forb}(F_{1},\ldots,F_{k})$ has a $<$-universal element —equivalently,
the problem of whether there is a countable graph $G\ $with
$\mathrm{Ex}(G)=\\{F_{1},\ldots,F_{k}\\}$— algorithmically decidable?

## References

  * [1] J. Carmesin.  Embedding simply connected 2-complexes in 3-space I.  Preprint 2017.
  * [2] R. Diestel, R. Halin, and W. Vogler.  Some remarks on universal graphs.  Combinatorica, 5(4):283–293, 1985.
  * [3] R. Diestel and D. Kühn.  A universal planar graph under the minor relation.  Journal of Graph Theory, 32(2):191–206, 1999.
  * [4] R. Diestel and R. Thomas.  Excluding a Countable Clique.  J. Combin. Theory (Series B), 76(1):41–67, 1999.
  * [5] Reinhard Diestel.  Graph Theory _(3rd edition)_.  Springer-Verlag, 2005.
Electronic edition available at:
http://www.math.uni-hamburg.de/home/diestel/books/graph.theory.

  * [6] A. Georgakopoulos.  Infinite highly connected planar graphs of large girth.  Abh. Math. Sem. Univ. Hamburg, 76(1):235–245, 2006.
  * [7] A. Georgakopoulos.  On planar Cayley graphs and Kleinian groups.  Trans. Am. Math. Soc., 373:4649–4684, 2020.
  * [8] A. Georgakopoulos and G. Kontogeorgiou.  Discrete group actions on 3-manifolds and embeddable Cayley complexes.  arXiv:2208.09918.
  * [9] C. W. Henson.  A family of countable homogeneous graphs.  Pacific Journal of Mathematics, 38(1):69–83, July 1971.  Publisher: Mathematical Sciences Publishers.
  * [10] T. Huynh, B. Mohar, R. Šamal, C. Thomassen, and D. R. Wood.  Universality in minor-closed graph classes.  arXiv:2109.00327.
  * [11] W. Imrich.  On Whitney’s theorem on the unique embeddability of 3-connected planar graphs.  In Recent Adv. Graph Theory, Proc. Symp. Prague 1974, pages 303–306. 1975.
  * [12] P. Komjath, Mekler A., and J. Pach.  Some universal graphs.  Israel J. Math., 64(1):158–168, 1988.
  * [13] P. Komjath and J. Pach.  Universal elements and the complexity of certain classes of infinite graphs.  Discrete Mathematics, 95(1):255–270, 1991.
  * [14] T. Krill.  Universal planar graphs for the topological minor relation.  arXiv:2203.12643.
  * [15] D. Kühn.  Minor-universal planar graphs without accumulation points.  J. Graph Theory, 36(1):1–7, 2001.
  * [16] I. Křìž and R. Thomas.  Clique-sums, tree-decompositions and compactness.  Discrete Mathematics, 81(2):177–185, April 1990.
  * [17] F. Lehner.  Universal planar graphs for the topological minor relation, 2022.  arXiv:2203.03477.
  * [18] L. Matthiesen.  There are uncountably many topological types of locally finite trees.  J. Combin. Theory (Series B), 96(5):758–760, 2006.
  * [19] B. Mohar.  Tree amalgamation of graphs and tessellations of the cantor sphere.  J. Combin. Theory (Series B), 96(5):740–753, 2006.
  * [20] J. Pach.  A problem of Ulam on planar graphs.  Europ. J. Comb., 95(2):357–361, 1981.
  * [21] T. D. Parsons, G. Pica, T. Pisanski, and A. G. S. Ventre.  Orientably simple graphs.  Mathematica Slovaca, 37(4):391–394, 1987.
  * [22] R. Rado.  Universal graphs and universal functions.  Acta Arithmetica, 9(4):331–340, 1964.
  * [23] N. Robertson, P. Seymour, and R. Thomas.  Excluding infinite minors.  Discrete Mathematics, 95(1):303–319, 1991.
  * [24] N. Robertson, P. Seymour, and R. Thomas.  Sachs’ linkless embedding conjecture.  J. Combin. Theory (Series B), 64:185–227, 1995.
  * [25] N. Robertson and P. D Seymour.  Graph Minors: XVII. Taming a Vortex.  J. Combin. Theory (Series B), 77(1):162–210, 1999.
  * [26] N. Robertson and P. D. Seymour.  Graph Minors. XX. Wagner’s conjecture.  J. Combin. Theory (Series B), 92(2):325–357, 2004.
  * [27] N. Robertson, P. D. Seymour, and R. Thomas.  Excluding Infinite Clique Minors.  Memoirs of the AMS, 566, 1995.
  * [28] R. Thomas.  Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor.  Trans. Am. Math. Soc., 312(1):279–313, 1989.
  * [29] H. van der Holst and R. Pendavingh.  On a graph property generalizing planarity and flatness.  Combinatorica, 29(3):337–361, 2009.
  * [30] K. Wagner.  Über eine Eigenschaft der ebenen Komplexe.  Mathematische Annalen, 114(1):570–590, December 1937.
  * [31] J. W. T. Youngs.  Minimal Imbeddings and the Genus of a Graph.  Journal of Mathematics and Mechanics, 12(2):303–315, 1963.