# Prove that for graphs $H$ and $G$, $\chi(G)$ + $\chi(H)$ = $\chi(G+H)$, where $G+H$ is the graph join

I have an idea of how to prove this but I am stuck on how to show part of my argument. I know how to show that $$G+H$$ is ($$m+n$$)-colorable, where $$\chi(G)=m$$ and $$\chi(H)=n$$, but I am unsure how to show that $$G+H$$ is not $$k$$-colorable, for $$k.

No color in a coloring of $$G+H$$ can use the same color for a vertex of $$G$$ and a vertex of $$H$$, because every vertex of $$H$$ is connected to every vertex of $$G$$ in $$G+H$$. Thus we have to use $$\chi(G)+\chi(H)$$ colors,$$\chi(G)$$ to color $$G$$, and $$\chi(H)$$ to color H.

• That's what I was thinking of. My problem was I wasn't sure how to explain that what you wrote is sufficient to conclude that you need χ(G)+χ(H) colors. Because you could still have vertices of the same color in the part of G+H that came from G. I realize that this must be restricted by the condition on χ(G), but I'm not sure how I can conclude that straight away. Thanks for your answer. – A.B Dec 2 '19 at 2:29