# In ZF, are there infinite planar graphs that are not 4-colorable?

This is a follow-up to: Are infinite planar graphs still 4-colorable?

Specifically, absent the axiom of choice, is there an explicit example of an (probably uncountably) infinite planar graph that is not 4-colorable?

• What's your definition of 'planarity'? I would expect that any reasonable definition here would lead to a well-ordering on the graph nodes... Mar 4 '20 at 19:12
• I suspect that any answer may depend on the definition of planarity, and I will refrain from imposing any particular definition; I am just interested in any relevant example. Why would a well-ordering of nodes be particularly important? Mar 4 '20 at 19:35
• A graph $(V, E)$ is called planar if there are maps $f: V\to \mathbb{R}^2$ and $g$ from $E$ to the set of arcs in $\mathbb{R}^2$ such that the arc correspnding to an edge $(a,b)$ connects $f(a)$ and $f(b)$ . and no two arcs $g(e)$, $g(e')$ intersect except at end points providef $e\ne e'$. Is there a different definition?
– user6976
Mar 4 '20 at 19:53
• @Mark One might want to consider rather than a global embedding only local ones. Mar 4 '20 at 19:56
• @StevenStadnicki Sorry, that was a blindingly stupid moment on my part. Consider the graph with vertex set $\mathbb{R}\times\{1,2\}$ and edge relation given by $(a,b)E(c,d)$ iff $a=c$. I don't see how this wouldn't be considered planar, but $\mathbb{R}$ isn't well-orderable in ZF alone. Mar 4 '20 at 20:06