Consider an undirected simple planar graph, with these additional restrictions:
- The plane in which the graph is embedded has a Cartesian coordinate system, and there's an injective function mapping each node to its pair of coordinates. I.e., no two nodes lie on the same point of the plane.
- Each node maps to integer coordinates. I.e., the nodes lie on a grid.
- For any node, call it $A$, all neighbors of $A$ lie on a circle centered on $A$. I.e., all neighbors of any node have the same distance to that node.
I couldn't draw a graph like this with max degree greater than $4$, so I'm wondering whether $4$ is indeed the max degree for this set of graphs. If not $4$, perhaps it's $5$ or $6$?
Edit: now I mechanically found the maximal degree of a graph from this set to be 16, so the conjecture is disproved. It would still be nice if someone gave an answer that explains this intuitively.
Using the Brahmagupta-Fibonacci identity you can find integers that are written as the sum of two squares in arbitrarily many ways. For example from $5^2=3^2+4^2$ and $13^2=5^2+12^2$ we get $65^2=63^2+16^2=56^2+33^2$.
From this you can make a star graph, centre at $(0,0)$, connected to $20$ equidistant vertices at $(\pm65,0)$, $(0,\pm65)$, $(\pm63,\pm16)$, $(\pm16,\pm63)$, $(\pm56,\pm33)$, $(\pm33,\pm56)$.
By multiplying this by for example $17^2=8^2+15^2$ you find that there are $36$ grid points at a distance of $65\cdot17=1105$ from the origin.