greetings. a matchstick graph is a planar graph whose edges are unit line segments. the smallest 2- and 3-regular matchstick graphs are easy to find. http://www.stetson.edu/~efriedma/mathmagic/1205/d23.gif the smallest known 4-regular matchstick graph (credited to H. Harborth and M. Timm) is more surprising. http://www.stetson.edu/~efriedma/mathmagic/1205/d4.gif there is no 5-regular matchstick graph. i'm interested in matchstick graphs whose vertices have two different degrees. what's the smallest matchstick graph with vertices of degrees m and n (m<n) ? has anyone considered this problem before? i think i know the answers for m=1, m=2, and m=3 n<=12. let f(m,n) be the minimum number of matchsticks necessary. f(1,n) = n f(2,n) = 3n/2 for n<=10 even f(2,n) = 2n-5 for n>=12 even f(2,n) = 3n-4 for n<=9 odd f(2,n) = 4n-13 for n>=11 odd f(3,4) = 14 f(3,5) = 16 f(3,n) = 5n-18 for 6<=n<=12 i am particularly interested in possible answers for m=4. surely someone can do better than i have. http://www.stetson.edu/~efriedma/mathmagic/1205/d4,5.gif http://www.stetson.edu/~efriedma/mathmagic/1205/d4,6.gif the same question is perhaps more interesting (and definitely more challenging) if we require the matchstick graph to have equal numbers of vertices of degrees m and n. let g(m,n) be the minimum number of matchsticks necessary. my best results are: g(1,2) = 3 g(1,3) = 6 g(1,4) = 20 g(1,5) = 156 (these come from adding one edge to each vertex of a regular graph) g(2,3) = 5 g(2,4) = 9 g(3,4) = 21 again, the ones i'm most interested in are the larger ones. can someone improve these? can anyone find any such graph with m=2 n=7? how about m=4 n=5? http://www.stetson.edu/~efriedma/mathmagic/1205/dd2,5.gif http://www.stetson.edu/~efriedma/mathmagic/1205/dd2,6.gif http://www.stetson.edu/~efriedma/mathmagic/1205/dd3,5.gif http://www.stetson.edu/~efriedma/mathmagic/1205/dd3,6.gif any improvements, comments, or references would be appreciated. erich friedman stetson university