mfb wrote:This can be extended, to show that in a hypothetical unit-distance graph that cannot be 4-colored, every point needs to be connected to at least 4 other points.

No, this direction does not work. For every unit-distance graph that cannot be 4-colored, you can add a new vertex which is connected to a single other vertex only. The new graph cannot be 4-colored, but one vertex has just one edge.

However, if there is a graph which cannot be 4-colored, you can remove all points with less than 4 edges, without losing this property.

Oops, sorry, I meant that for every graph that cannot be 4-colored, either every point has four points that it is connected to, or that there is a sub-graph of that graph that cannot be four colored such that every point is connected to four other points. I am interested in a minimal graph that cannot be four-colored, not all the other graphs that can be made from that graph by attaching new vertices. I thought it would be useful to list on this forum any unit-distance graphs you can think of that cannot be embedded in the plane. Labeling the points A, B, C, etc and listing the vertices of the unembeddable graphs, I have:

The tetrahedron: {AB,AC,AD,BC,BD,CD}

I don't exactly know what to call this, so I'll just call it U

_{1}: {AB,AC,AD,BE,CE,DE}

Edit: I just came up with a whole class of unembeddable graphs:

pentagonal pyramid:{AB,AC,AD,AE,AF,BC,BF,CD,DE,EF}

septagonal pyramid:{AB,AC,AD,AE,AF,AG,AH,BC,BH,CD,DE,EF,FG,GH}

and so on, basically, A is connected to every point, B is connected to the last point, and every point is connected to the point before or after it in the loop of all points but A. This doesn't work with 7 points (including A), because that is just a hexagon with A in the middle.

Any more you can think of? I didn't include the square pyramid on purpose because it turns out that U

_{1} is a sub-graph of the square pyramid.

Also, I have a proof that any unit-distance graph that is unembeddable in the plane must have a point that is connected to at least 3 other points. It goes as follows: assume that it is possible to have an unembeddable graph that has no points connected to more than 2 other points. Every point that is only connected to one other point can be removed from the graph without compromising its unembeddability, so we can assume that every point is connected to exactly 2 other points. no small loops can exist in the graph, because then every point in that sub-graph is connected to 2 other points in that sub-graph, and it cannot be connected to the rest of the original graph, meaning that either the sub-graph, or the rest of the graph, can be removed from the graph. This means that there is one big loop in the graph, containing all the points.

However, this can be embedded as a polygon in the plane, therefore there is no minimal graph satisfying the assumptions, therefore there is no graph such that every point is connected to at most two other points that is not embeddable in the plane.

I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.