Show that $K_n$ is not the union of two planar graphs

Question

Show that $K_n$ is not the union of two planar graphs for $n\ge 11$

I know that a graph $G$ is planar iff it does not have $K_5$ or $K_{3,3}$ as its induced subgraphs

But how to use it in the above problem.

Please help.

Answer 1

IF by union you mean just put two graph that don't share any vertices together then that is super easy. Suppose $K_n$ is the union of two planar graph, then $K_n$ is planar. We know that for a planar graph $G$, $|E(G)|\leq 3|V(G)|-6$. A complete graph with more than $11$ vertices has more than $\binom{11}{2}=55$ edges. and in general a graph $G$ on $n$ vertices has $\binom{n}{2}$ edges. So combining the above inequality to get $\frac{n(n-1)}{2}=\binom{n}{2}=|E(G)| \leq 3n-6$. We know that quadratic grows faster than linear, so left side of inequality grows faster than right side. In particular, when $n \geq 11$, it doesn't hold anymore. One can check $55=\frac{11*10}{2} >27=33-6$. This is probably over complicated but it is the same argument to show the following.

If you mean two graph $H,K$ sharing all the vertices but different edges. Then because they are planar, we have $|E(H)|\leq 3|V(H)|-6$ and $|E(K)|\leq 3|V(K)|-6$.Now, Add those to get $|E(G)|\leq 6|V(G)|-12$. but then $\frac{n(n-1)}{2}=\binom{n}{2}=|E(G)| \leq 6n-12$ which means $n(n-1) \leq 12n-24$. But again left side is quadratic and right is linear and quadratic grows faster than linear. And we can check for $n=11$ we get by substituting into the previous inequality :$110 \leq 108$ which is not possible. And the bigger root of $n^2-13n+24=0$ is $\frac{13 \pm \sqrt{13^2-4*24}}{2}=\frac{13 \pm \sqrt{73}}{2} \approx \frac{13+8}{2} \approx 10.5 $. So anything after the root, you have left side greater than right side.

I hope this is correct. Here is the graph of the function of the two side of inequalities where we can see the the quadratic grows faster than linear after $n \approx 10.77$: