If a graph with m nodes is complete and planar, all graphs with m nodes are planar.

Question

How can I prove that if a there exists a complete graph with $m$ nodes that is planar, then all graphs with $m$ nodes must be planar. I know a complete planar graph has at most 4 nodes, and I think I could show it using that, but I assume there is a more direct route.

Answer 1

All planar graphs satisfy the criteria

$$ |E| \leq 3 |V| - 6 $$

If we pick a particular value of $|V| = n$ (that is, we pick the number of vertices $n$), the maximum number of edges will be posessed by the completed graph on $k$ vertices - $K_n$

Hence, the maximum value of $|E|$ for a given $|V| = n$ is $E[K_n] = \binom{n}{2}$ (no. of edges of $K_n$)

So, if for $K_n$, $$|E[K_n]| \leq 3|n| - 6$$

Then any other graph of $n$ vertices, say $G$ will have $$E[G] \leq E[K_n]$$ and hence

$$ E[G] \leq E[K_n] \leq 3|n| - 6 $$ which means that $G$ is also planar since it satisfies the characteristic