Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

It seems the following.

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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.