The union of two simple planar graph have chromatic number $\leq 12$ Consider of graph $G$ being the union of two simple planar graph both on the same set of vertices. I want to show $\chi(G) \leq 12$.
Four colour theorem indicates that the chromatic number of a planar graph is less than 4, and for general graphs $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$.  But this would only yield an upper bound of 16. Is there anything particular to planar graph that helps to reduce the bound?
 A: Planar graphs satisfy $|E(G)| \le 3|V(G)|-6$, so the union of two planar graphs satisfies $|E(G)| \le 6|V(G)|-12$, which we can use to show that there is a vertex of degree less than $12$.
This leads us to a proof by induction: remove that vertex, color the rest, and then color that vertex. The inductive hypothesis applies because any subgraph of $G$ is also a union of two planar graphs: the corresponding subgraphs of $G_1$ and $G_2$.
A: Since $G_1$ and $G_2$ are planar, we have $|E(G_1)| \le 3|V(G_1)|-6$ and $|E(G_2)| \le 3|V(G_2)|-6$. Since $V(G_1) = V(G_2)$ given, let $V = V(G_1) = V(G_2)$ for convenience. Then we have
$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$
Now, by Handshaking Lemma, we also know that
$$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$
So, one can easily see that there exists a vertex $v \in V$ such that $d_{G_1 \cup G_2}(v) < 12\ (*)$. Now, we will use induction on $|V|$.
Now, if $|V| = 1$, the result is clear (actually it is clear for $|V| \le 12$). Now, suppose inductively it holds for planar graphs with $|V| = n$. Then, for a vertex set with $|V| = n+1$, consider a graph with vertex set $V-v$ (Note that removing a vertex cannot make a planar graph non-planar). Then, by induction hypothesis, we can color this graph with at most $12$ colors. Now add $v$ back with the removed edges. By $(*)$, $d_{G_1 \cup G_2}(v) < 12$ so we can color this vertex with at least one of the colors used in the graph with vertex set $V-v$ and we are done.
