Apparently you are correct. http://www2.math.technion.ac.il/~room/ps_files/matchstick.pdf has Theorem 1. Finite 5-regular matchstick graphs do not exist. I thought it was funny that the wikipedia article had a link to a paper https://arxiv.org/abs/math/0609360 whose abstract says "The Harborth graph is the smallest known example of a 4-regular planar unit-distance graph." where "4-regular planar unit-distance graph" is exactly the search term I was using. On Tue, May 10, 2016 at 6:53 PM, Warren D Smith <warren.wds@gmail.com> wrote:

...

From: Veit Elser <ve10@cornell.edu> https://en.wikipedia.org/wiki/Matchstick_graph "Harborth graph"

--in order for a K-regular matchstick graph to exist with N vertices, we need 2N coordinates to satisfy K*N/2 equations.

And actually the first two vertices can wlog be located at (0,0) and (1,0) in which case 2N-4 coordinates must satisfy K*N/2-1 equations.

The #equations is arbitrarily greater than the #unknowns if K>=5 when N=large, therefore perhaps K>=5 is impossible? If K=4 it also is greater, but only by 3, so a few miracles like Harborth's could be hoped for.

-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun