Sum of critical graphs is critical

Let $$G_1$$ and $$G_2$$ be $$k_1$$ and $$k_2$$ critical respectively. That is $$\chi(G_1) = k_1$$ and $$\chi(G_2) = k_2$$ and the removal of any vertex or edge reduces the chromatic number. I am trying to prove that the sum $$G = G_1+G_2$$ is $$(k_1+k_2)$$ critical. $$G$$ is the graph obtained by connecting every vertex in $$G_1$$ to every vertex in $$G_2$$.

Now it is clear that colouring $$G$$ by applying a proper $$k_1$$ coloring to $$G_1$$ and a proper $$k_2$$ coloring $$G_2$$ is the best we can do, so we have that $$\chi(G) = k_1 + k_2$$. It is also evident that removing an edge or vertex from either $$G_1$$ or $$G_2$$ would reduce the chromatic number since both graphs are critical. It remains to show that removing one of the edges between $$G_1$$ and $$G_2$$ also reduces the chromatic number. However, this is where I am stuck. I don't see how I may remove one such edge and obtain a proper $$k_1 + k_2 -1$$ coloring.

Any help would be appreciated:)

• Out of curiosity, where did you encounter this result? I would expect that most standard texts would cover this. But I didn't find such a result anywhere. Apr 20 at 13:42
• It showed up in the notes from a course I'm following. I agree, I'm surprised I didn't find it anywhere else Apr 20 at 14:01

Let's say we remove an edge $$xy$$ with $$x$$ a vertex in $$G_1$$ and $$y$$ in $$G_2$$. Since $$G_1$$ is $$k_1$$ critical, we may choose a $$k_1-1$$ coloring on the graph $$G_1'$$ obtained by removing the vertex $$x$$. By the same argument, we choose a $$k_2-1$$ coloring on $$G_2'$$ obtained by removing the vertex $$y$$.
Then just pick a color that is neither in among the $$k_1 - 1$$ colors on $$G_1'$$ nor $$k_2-1$$ colors on $$G_2'$$ and assign it to both vertices $$x$$ and $$y$$. Since we removed the edge $$xy$$, we obtain this way a valid coloring which has $$k_1+k_2-1$$ colors.
I think it's something like this. Let $$G_1$$ and $$G_2$$ be the graphs respectively and $$v \in V(G_1)$$, $$w \in (G_2$$). Let $$e = vw$$, and say $$e$$ is the edge removed.
Consider $$G_1 - v$$, which by color criticality is $$(k_1 - 1)$$-colorable. Similarly, $$G_2 - w$$ is $$(k_2 -1)$$-colorable. Use $$k_1 + k_2 - 2$$ colors to color $$(V(G_1) - v) \; \sqcup (V(G_2) - w)$$ in the obvious way, and use the $$(k_1 + k_2 - 1)$$-th color to color $$v$$ and $$w$$. Now, in $$(G_1 + G_2) \setminus e$$, the only vertices with color $$(k_1 + k_2 - 1)$$ are $$v$$ and $$w$$, which happen to be non-adjacent.