Let G and H be two graphs.
Prove that χ (G+H) = χ(G) + χ(H),
where χ(G) represents the chromatic number of G and χ(H) represents the chromatic number of H, and
χ(G+H) is the join of the two graphs.
I understand that the chromatic number is the smallest number k such that the graph is k-colourable, and that when colouring a graph no two adjacent vertices can be the same colour.
I also know that the join of these two graphs means that every vertex in G must be joined by an edge to every vertex in H.
I understand the proof in my head- I think - but only very messily. For every pair of vertices of which one is in G and one is in H, the edge that joins them in means that they cannot be of the same colour. Because of this, you simply have to add the chromatic numbers of each graph before the joining to get the chromatic number in the new joint graph.
I am looking for help to write this out in proper proof form and not just a bunch of assumptions!
Thanks
The first stage in properly proving it is to formalize the logic. There are two aspects to the question here: you want to show that $\chi(G+H)\geq \chi(G)+\chi(H)$ — which is to say, the chromatic number of the combined graph is at least as big as the sum — and also that $\chi(G+H)\leq \chi(G)+\chi(H)$. The latter is a little bit easier; you 'just' have to exhibit a coloring of $\chi(G+H)$ using $\chi(G)+\chi(H)$ colors. Your idea is the right one, but can you see how to formalize the notion of using a different set of colors for $H$? (It may help to 'number' your colors, rather than name them...)
As for showing $\chi(G+H)\geq\chi(G)+\chi(H)$, you can formalize your thinking into an argument by contradiction. First show that the color sets of the two graphs have to be disjoint — your argument is basically good here — and then argue that any coloration of $G+H$ with fewer than $\chi(G)+\chi(H)$ colors would lead to either a coloration of $G$ with $\lt\chi(G)$ colors, or a coloration of $H$ with $\lt\chi(H)$ colors.