A short proof of the existence of a minor-universal countable planar graph

We order the edges of $G$. By the infinite version of Menger’s Theorem ([1]), there exists a cycle $C$ that contains $e_{0}$. Set $G_{0}:=C$. Given $G_{n-1}$, we determine $G_{n}$ as follows. If $G_{n-1}=G$, then set $G_{n}:=G$. Otherwise, let $e$ be the edge outside of $G_{n-1}$ with the smallest index. It is a well-known exercise that there exists a cycle $C_{e}$ in $G$ that contains both $e$ and $e_{0}$. Let $P_{e}$ be the subpath of $C_{e}$ that meets $G_{n-1}$ only at its endpoints and contains $e$. Set $G_{n}:=G_{n-1}\cup P_{e}$. To see that $G=\bigcup_{n=0}^{\infty}G_{n}$, note that $e_{n}\in G_{n}$.

∎

Let $J$ be an $n$-slice and $S$ be a separator of $J$. We say that a connected component is $N$-coarse for $N\geq n$ if its torso in $J$ is the union of a finite set of $N$-pieces. Since $S$ is finite, it is entirely contained in some $\mathcal{G}_{N}$ for $N\geq n$, so it splits $J$ into $N$-coarse components. Therefore $S$ must have order at least $N+3\geq n+3$, since $N+3$ is half the length of an $N$-diameter rounded up, which is the shortest boundary that an $N$-coarse component can have with its complement in $J$. ∎

Let $G$ be a plane graph as in the statement of Lemma 2. We will construct a subgraph $H$ of $\mathcal{G}$ that is an $IG$. In particular, we will define $H$ as the union of a sequence $H_{n}$ of $IG_{n}$, where $(G_{n})_{n\in\mathbb{N}}$ is an ear decomposition of $G$ (Claim 1), such that for every $n\in\mathbb{N}$, $v\in V(G)$, and $e\in E(G)$, we have for the corresponding maps that $\phi_{n}(v)\subseteq\phi_{n+1}(v)$ and $\phi_{n}(e)=\phi_{n+1}(e)$. This will allow us to define $\phi:G\rightarrow H$ by setting $\phi:=\bigcup_{n=0}^{\infty}\phi_{n}$; the reader is invited to check that this yields an IG. To satisfy these constraints, we also require a consistent way to correspond abstract faces of $G_{n}$ to slices of $\mathcal{G}$. To keep notation simple, we overload our maps $\phi_{n}$ to also perform this function.

The following definition is key in our analysis: given a face $F$ of $G_{n}$, we denote by $V_{F}$ the set of vertices of $\partial F$ that are ends of ears contained in $F$. Note that, since $G$ is sub-cubic, each vertex can be the end of at most one ear.

We construct inductively the sequence $\phi_{n}$ with the additional useful requirements that for each $v\in V(G_{n})$, $\phi_{n}(v)$ is a path, and that for each face $F$ of $G_{n}$, the slice $\phi_{n}(F)$ is $|V_{F}|$-connected and intersects $H_{n}$ only at one end vertex of each of the paths $\{\phi_{n}(v)|v\in\partial F\}$ and in the correct cyclic order.

For the base case, suppose that $G_{0}$ has length $l_{0}\geq 3$. We consider two disjoint face cycles $C_{0}$ and $C^{\prime}_{0}$ of the graph $\mathcal{G}_{l_{0}}$, contained in the same ($l_{0}-2$)-piece, noting that each has length $2l_{0}+3>l_{0}$. By Menger’s Theorem and Claim 2, we may also consider $l_{0}$ disjoint paths inside the piece joining $C_{0}$ and $C^{\prime}_{0}$. We define $\phi_{0}$ by mapping the vertices of $G_{0}$ to these paths in the correct cyclic order, each edge of $G_{0}$ to an appropriate (open) subpath of $C_{0}$, and the two faces $F_{0}$ and $F^{\prime}_{0}$ of $G_{0}$ to the two $l_{0}$-slices $J_{0}$ and $J^{\prime}_{0}$ bounded by $C_{0}$ and $C^{\prime}_{0}$, respectively. Both $J_{0}$ and $J^{\prime}_{0}$ are $(l_{0}+3)$-connected, and $l_{0}+3>l_{0}=|V_{F_{0}}|+|V_{F^{\prime}_{0}}|$, so $F_{0}$ is mapped to a $|V_{F_{0}}|$-connected slice and $F^{\prime}_{0}$ is mapped to a $|V_{F^{\prime}_{0}}|$-connected slice.

For the inductive step, suppose that we have defined $\phi_{n-1}$ so that each vertex $v$ is mapped to a path $\phi_{n-1}(v)$ and each face $F$ is mapped to a $|V_{F}|$-connected slice $\phi_{n-1}(F)$ that intersects $H_{n-1}$ only at one end vertex of each of the paths $\{\phi_{n-1}(v)|v\in\partial F\}$ and in the correct cyclic order.

Let $F$, of boundary length say $l$, be the unique (Remark 1) face of $G_{n-1}$ such that the $n^{th}$ ear $G_{n}\setminus G_{n-1}$, of length say $L$, lies within $F$, splitting it to two faces $F^{\prime}$ and $F^{\prime\prime}$. Let $f$ be a face of $\mathcal{G}_{N}$ for some $N>n$ such that $f$ is bounded by the slice $\phi_{n-1}(F)$, has diameter length at least $L$, and all its slices have connectivity at least $2L+l$ (e.g. take $N=2L+l-3$) (Claim 2).

By the inductive hypothesis, $\phi_{n-1}(F)$ is $|V_{F}|$-connected. By Menger’s Theorem, there exist disjoint paths $(P_{v})_{v\in V_{F}}$ in $\phi_{n-1}(F)$ such that $P_{v}$ begins at the vertex $\phi_{n-1}(v)\cap\phi_{n-1}(F)$ and ends at some $p(v)\in\partial f$. In particular, since $\mathcal{G}$ is a plane graph, $p$ preserves the cyclic order of $\phi_{n-1}(V_{F})$. We also denote by $D$ the diameter of $f$ with ends $p(x)$ and $p(y)$, where $x$ and $y$ are the ends of the ear $G_{n}\setminus G_{n-1}$.

For $v\in V_{F}$ we set $\phi_{n}(v)=\phi_{n-1}(v)\cup P_{v}$. The vertices of the ear $G_{n}\setminus G_{n-1}$ we map arbitrarily (but in the correct order) to single vertices of $D$. Each edge of the ear is mapped to the subpath of $D$ between the images of its ends. The faces $F^{\prime}$ and $F$ are mapped to the corresponding slices induced on $f$ by $D$. Every other vertex, edge, or face of $G_{n}$ has the same image under $\phi_{n}$ as under $\phi_{n-1}$.

Firstly, it follows from the construction that $\phi_{n}:G_{n}\rightarrow H_{n}$ is an $IG_{n}$.

Moreover, for $v\in V_{F}$, by the inductive hypothesis, $\phi_{n-1}(v)$ is a path. Also, $P_{v}$ is a path and, again by the inductive hypothesis, $\phi_{n-1}(v)\cap P_{v}$ is a single vertex. Therefore, $\phi_{n}(v)$ is a path. Trivially, the same holds for vertices in $V(G_{n})\setminus V_{F}$.

Additionally, both $F^{\prime}$ and $F^{\prime\prime}$ are mapped to slices of connectivity $2L+l$. Since $|V_{F^{\prime}}|+|V_{F^{\prime\prime}}|\leq|\partial F^{\prime}|+|\partial F^{\prime\prime}|=2L+l$, both of these slices are adequately connected. We have also ensured that they intersect the appropriate vertex images under $\phi_{n}$ only at one end vertex each and in the correct cyclic order. These same properties hold, by the inductive hypothesis, for every other face image of $G_{n}$. This concludes the induction, and the proof of Lemma 2.

∎