I have recently been introduced to graph theory, and there is that one idea I have which I am struggling with. I would like to know if this is true, and whether or not there is a somewhat simple proof for it (or for some of the simpler cases). By colorable with $n$ colors I mean that the vertices can be colored so that no two adjacent vertices are of the same color.
Can we say that a graph is colorable with $k$ colors if and only if there is no $k+1$ vertices complete subgraph to it?
It is simple for the implication, but for the other way, I feel like there are many subtle situations I am not able to grasp. I have also tried to find counter-examples, by creating "locked" graphs in which the colors can't be interchanged and then introducing new vertices, but without success.
I am also interested in the simple cases, for which I also have no clue, such as when $k=2$.
No, this doesn't work. Take, for instance, a cycle on five vertices; it certainly doesn't contain a triangle (complete graph on three vertices), but it requires at least three colors.