I was solving this question related to vertex colorings. In the solution part of the question it says that:
"The coloring is optimal because the graph contains the complete graph (clique) K4."
Also in another question, the same explanation goes:
"The coloring is optimal because the vertices 1 to 5 form a complete subgraph K5."
Why a vertex coloring (or edge coloring too? ) has to be optimal since it contains a complete graph? I have gone through all my lecture notes and slides but there is no such an information.
Thanks for your help, in advance!
These arguments work in a quite specific case. They show that the first graph cannot have a colouring with fewer than 4 colours, and the second graph cannot have a colouring with fewer than 5 colours. So any 4-colouring of the first graph is optimal, and any 5-colouring of the second graph is optimal.
A graph that contains K4 can never be coloured with fewer than 4 colours, because that subgraphs forbids it. K4 has four nodes all connected to each other, so each of them has to have a different colour, so you need 4 colours just for that subgraph. If that subgraph already needs 4 colours, the entire graph definitely does - though perhaps it needs more (in that case you'd need a different kind of proof of optimality).
An other way to look at the graph colouring constraints, perhaps helpful in this case, is to interpret every clique as an all-different constraint.