# Prove that a graph is 10-colorable

Let $G_1 = (V, E(G_1))$, $G_2= (V, E(G_2))$ be acyclic graphs and $H = (V, E(H))$ be a planar graph on the same group of vertices $V$.

Prove that $G = (V, E(G_1) \cup E(G_2) \cup E(H))$ is 10-colorable.

Got any ideas?

Suppose $G$ is a graph such that any (not necessarily spanning) subgraph of $G$ contains a vertex of degree at most $d$. Then you can $(d+1)$-colour $G$: remove a vertex $v$ of minimum degree, colour the rest (by induction), and then use an available colour on $v$ (which exists, since $v$ has at most $d$ neighbours).
Hence it would suffice to show that for any subset $S \subseteq V$, $G|_S$ has minimum degree at most $9$. The minimum degree is always bounded above by the average degree. Can you use the fact that $G_1$ and $G_2$ are acyclic, and the fact that $H$ is planar, to get what you need?