See the article "Matchstick graph" on Wikipedia. The 104-vertex example is due to Heiko Harborth. There is a picture of it in the article. Note that its minimality has not been proven. You left out the requirement that the line segments not cross; without this constraint, there is an orthographic projection of the edges of a 4-cube that works with 16 vertices. I have an idea that computer search might settle the minimality question. On Tue, May 10, 2016 at 5:29 PM, Paul Palmer <paul.allan.palmer@gmail.com> wrote:
(Delurking for my first post.)
A while back I saw a fact posted (on Pat's Blog, if anyone reads it) that said:
104 is the lowest known number of unit line segments that can exist in the plane, 4 touching at every vertex.
I can find this repeated all over the internet, but nothing more about it.
I read it as saying that the smallest 4-valent (quartic) unit distance graph has 104 vertices.
Does that sound correct? Does anyone know where this might have come from?
Thanks. I have enjoyed following the discussions on this list. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun