Why is it not the case that: $K_5 \notin G \iff $ G is 4-colourable.

Question

Clearly $K_5 \in G \Rightarrow$ G not 4 colourable. For the converse I can't really get my head around but it seems intuitively true.

Let $G(V,E)$ consist of $V=\{X\}$, $E=\emptyset$. Add 4 vertices $x_i$, $i=1,2,3,4$ to $V$ and edges $\{X,x_i\}$ to $E$. Now continue to add vertices $y_j$ with $j\in \mathbb{N}$ to $V$ and edges $\{x_{i_a},x_{i_b} \}$ or $\{x_i ,y_j \}$ as desired. Note if adding vertex $y_j$ and edge $\{x_i ,y_j \}$, then the coloring can always escape. E.g. there will always be a possibility to 4 color. This continues until either $K_5$ appears in the graph, or we stop adding nodes/vertices.

Clearly there must be a problem here, but can anyone shed some light on the intuition here?

Answer 1

I guess the easiest argument against that kind of intuition would be to note that a circle with 5 edges/vertices is not 2-colorable, even though it does not contain a $K_3$.

Answer 2

Well, you are starting with a very specific graph as a base. You are also only adding edges in a specific way (never adding edges between two $y$ vertices, or between $X$ and a $y$ vertex). So your reasoning only considers a very small, very specific family of graphs.

There are very small graphs (7 vertices) that do not contain a $K_{5}$ but are not 4-colorable.