Coloring of overlaping graphs Let G1, G2, G3 be three (possibly overlapping) graphs on the same vertex set, and suppose that G1 can be properly colored with 2 colors, G2 can be properly colored with 3 colors, and G3 can be properly colored with 4 colors. Let G be the graph on the same vertex set, formed by taking the union of the edges appearing in G1, G2, G3. Prove that G can be properly colored with 24 colors.
 A: Let $A$ be the set of two colors for $G_1$, $B$ the set of colors for $G_2$, and $C$ the set of colors for $G_3$.
For $G$, we consider the set of colors $$A \times B \times C = \{(a, b, c) \mid a \in A, b \in B, c\in C\}.$$
Notice that $|A \times B \times C| = |A||B||C| = (2)(3)(4) = 24$ so it contains $24$ colors.
Now, for a vertex $v_0$ in $G$, we give it the color $(a_0, b_0, c_0)$ where $a_0$ is the color of $v_0$ in $G_1$, $b_0$ is the color of $v_0$ in $G_2$, and $c_0$ is the color of $v_0$ in $G_3$.
Now consider two vertices $v_1$ and $v_2$ that share an edge in $G$ with colors $(a_1, b_1, c_1)$ and $(a_2, b_2, c_2)$ respectively. Since $G$ is the union of edges in $G_1, G_2, G_3$, then that must be mean $v_1$ and $v_2$ share an edge in at least one of the $G_i$'s. Without loss of generality, suppose they share an edge in $G_1$. Since $G_1$ is properly colored, $v_1$ and $v_2$ have different colors in $G_1$, thus $a_1 \neq a_2$ and thus $(a_1, b_1, c_1) \neq (a_2, b_2, c_2)$ so $v_1$ and $v_2$ have different colors in $G$.
A: Hint. A proper coloring of a graph may be regarded as an equivalence relation on the vertex set, where the equivalence classes are independent sets; the number of colors is the number of equivalence classes. The intersection of those three equivalence relations is an equivalence relation, with (at most) how many equivalence classes?
