We are no going to consider different ways of coloring graphs. More precisely, we shall color the vertices of a graph, observing two rules: every vertex must be colored, and two vertices linked by an edge cannot be given the same color. If n is a natural number, then a graph is said to be n-colorable if it can be colored using n different colors, but not with few colors than n.

Which graphs can be colored in one color? It is easy to see that each vertex of the graph must be isolated. Here is the only one-colorable graph with 13 vertices:

Which graphs are 2-colorable? One can prove that these are exactly the bipartite graphs. Here is a complete bipartite graph with 5 vertices on one side and 4 on the other; it has been colored using just 2 colors.