# Prove that if 3 planar graphs with same vertices then $G =(V,E_1 \cup E_2 \cup E_3)$ is 18-colorable

Given: $G_1 = (V,E_1), G_2 = (V,E_2), G_3 = (V,E_3)$ three planar graphs on same vertices group $V$. Let $G = (V,E_1 \cup E_2 \cup E_3)$. Prove that $G$ is $18$-colorable.

What I did so far:

From a previous question I know that for each planar graph $G$ there is a partition of $V = V_1 \cup V_2 \cup V_3$ such that all $V_i$ are distinct, and the graph that is formed by each $V_i$ is acyclic. Now, I observe that we can divide each of the $G_i$ we have in the question to 3 partitions as mentioned. Thus, for each $G_i$ and its' partitions $G_{i_1}, G_{i_2}, G_{i_3}$ the graphs formed by those (individually) are $2$ colorable because there are no cycles. I observe again: if we have 9 parts, and each are $2$ colorable, then $9 \cdot 2 = 18$ might mean something or might even be the key to the question.

But right there is where I couldn't go on, I mean, I couldn't find a suitable way to mix these 9 parts to get our requested graph $G$ and in a way that it is $18$-colorable.

Any direction will be appreciated!

It suffice to show that each such a graph $G$ contains has a vertex $v\in V$ of degree $\deg v\le 17$, and then apply induction. Let’s show this. Clearly, $\sum_{v\in V}\deg v=2|E|$. Therefore there exists a vertex $V$ with a degree not greater than $2|E|/|V|$. By Euler Theorem, $|V|-|E_i|+|F_i|=2$ for each $i$, where $|F_i|$ is the family of the faces of the planar graph $G_i$. Since each face of the graph $G_i$ is an $n-$angle with $n\ge 3$, we see that $2|E_i|\ge 3|F_i|$, so $3|V|-|E_i|\ge 6$. Then $9|V|-|E|\ge 18$ and $2|E|/|V|\le 18-36/|V|$. Therefore there exists a vertex $V$ with a degree not greater than $17$.