In fact we can do a bit better; 3^floor(K/2)*2, by using triangles instead of rhombi; Warren's degree-of-freedom argument is evaded here in a similar way. I'm pretty sure that 1, 2, 3, 6 are the best achievable for K=0, 1, 2, 3 respectively. We can do K=4 with 9 vertices but I'm not sure we can't get away with fewer. On Tue, May 10, 2016 at 8:55 PM, Warren D Smith <warren.wds@gmail.com> wrote:

Allan Wechsler is of course correct, K-regular matchstick graphs exist with 2^K vertices and graphically the same as the K-cube. (if edge-crossings allowed.)

These evade my degree of freedom counting argument because his graph drawings "really" have very few, about 2K or fewer, degrees of freedom.

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