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:
- For any graph $G$ with at most $n$ vertices, we have $G \subseteq K_n$, and
- 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
- For any planar graph $G$ with at most $n$ vertices, we have $G \subseteq U_n$, and
- 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.
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.