Hey I am having trouble with this question (x(G) means chromatic number of G)



I am not sure how to use completeness but I think I need to show that I can find a critical subgraph in G that has the same chromatic number as G and then if I remove any two vertices then chromatic number goes down for each one.

Can anyone help me begin?

Thanks

Heres a quick proof.
Suppose G is not complete
If v and w are not connected, you can add them back to the graph. You will need to increase the chromatic number by at most 1.(why is this?). Let the chromatic number of G be X. If you remove them again you will see the you will not get X-2; but instead will get either X or X-1. A Contradiction

Thank you that helped a lot