A question about the four-color problem

Question

I remember there was a theorem in the history, concerning the four-color problem. It states something like following: in a map, the maximal number of regions that can be neighbors to each other is 4. However, this didn't prove the four-color theorem for some reason. What is the name of the theorem? I am trying to find the exact statement and the proof of this theorem, to understand why it didn't prove the four-color problem.

Answer 1

Four-color theorem states that any map in a plane can be colored using four colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. It also supposes that there are no exclaves. So in graph theory formulation, considering countries as vertices and common non-degenerate borders as edges, theorem states that each planar graph is 4-colorable.

You say that each planar graph doesn't have a subgraph isomorphic to $K_5$, and this is correct. But clique number gives only lower bound on chromatic number. You may consider the cycle $C_5$. It is $K_3$-free, but it is not $2$-colorable. Also there are $K_3$-free graphs with arbitrary high chromatic number.