# Planar analogues of complete graphs

In this question, the word graph means simple graph with finitely many vertices. We let $$\subseteq$$ denote the subgraph relation.

A characterization of complete graphs $$K_n$$ gives them as "$$n$$-universal" graphs that contain all graphs $$G$$ with at most $$n$$ vertices as subgraphs:

1. For any graph $$G$$ with at most $$n$$ vertices, we have $$G \subseteq K_n$$, and
2. given any graph $$H$$ that contains all graphs $$G$$ with $$|V(G)| \leq n$$ as subgraphs, we have $$K_n \subseteq H$$.

Question 1. (the probably-easy question) Are there planar graphs $$U_n$$ that are "$$n$$-universal" in the sense that

1. For any planar graph $$G$$ with at most $$n$$ vertices, we have $$G \subseteq U_n$$, and
2. given any planar graph $$H$$ that contains all planar graphs $$G$$ with $$|V(G)| \leq n$$ as subgraphs, we have $$U_n \subseteq H$$?

Obviously, there is a $$4$$-universal planar graph. I suspect the answer is negative for $$n > 5$$. If so, is there a quick proof?

Question 2. (the soft question) Are there any important results about sequences $$n\in\mathbb{N} \mapsto S_n$$ of planar graphs such that $$S_n$$ contains all at-most-$$n$$-vertex planar graphs as subgraphs? Most importantly:

• Known exact or asymptotic bounds on the minimum vertex number of $$S_n$$ as a function of $$n$$? Such exact bounds are known for trees. [1]
• Constructions of graphs achieving said bounds.

[1] F. R. K. Chung, R. L. Graham and D. Coppersmith: On trees which contain all small trees. The Theory and Applications of Graphs (ed. G. Chartrand) John Wiley and Sons, 1981, 265–272.

• For $n=5$, $K_5 - e$ is $5$-universal. May 9, 2021 at 15:03
• Thanks @MishaLavrov! I suspected so, but wasn't sure (which is why I hedged by writing $n > 5$). May 9, 2021 at 15:12

Just to answer the easy question:

For $$n=5$$, $$K_5 - e$$ is $$5$$-universal. Any $$5$$-vertex planar graph can be triangulated, extending it to a $$5$$-vertex planar graph with $$9$$ edges, which can only be $$K_5 - e$$. And since $$K_5-e$$ has $$5$$ vertices itself, every graph which contains all $$5$$-vertex planar graphs contains $$K_5-e$$.

For $$n>5$$, there are multiple possible $$n$$-vertex triangulations. For example, for $$n=6$$, there's these two graphs (#226 and #748 in the House of Graphs):

They're not drawn planarly, but this is not hard to fix.

Anyway, one planar graph that contains all the $$n$$-vertex planar graphs is the disjoint union of all $$n$$-vertex triangulations, and it is minimal: no proper subgraph of this disjoint union contains all $$n$$-vertex planar graphs. So if any graph will have the $$n$$-universal property, it's this one.

However, instead of taking the disjoint union, we can take a "wedge sum": pick a vertex $$v$$ in every $$n$$-vertex triangulation, and take a union which is disjoint except that all the $$v$$'s are the same. This is another planar graph that contains all $$n$$-vertex planar graphs, but it doesn't contain the disjoint union above.

So the disjoint union doesn't have the $$n$$-universal property; therefore, for $$n>5$$, no graph does.