The question Touching Matchsticks asked for the smallest matchstick graph where every node is connected to four distinct edges. The Harborth Graph is the smallest such, with 104 edges connecting 52 nodes.

Harboth Graph, not quite to scale

It is made of four identical (but for reflection) sections, each of whose shape, in isolation, would have one degree of freedom. Each section has two pairs of points that connect to other sections; drawing a line through each pair of points, the angle may be made greater than or less than ninety degrees; by the Mean Value Theorem, the angle may also be equal to ninety degrees, which is what's required for the shape to fit together with reflected copies of itself.

A curious feature of the Harboth Graph is that while it can be shown that four quarters of the Harborth graph drawn with the proper angles will fit together perfectly, it is impossible to produce the correct angles using compass and straightedge alone. If one were tasked with the task of drawing a regular matchstick graph of order four using compass and straightedge alone, what would be the smallest graph that could actually be constructed (determining the precise location of vertices using compass and straightedge alone)? A few different regular graphs, with various kinds of symmetry, can be compass-and-straightedge constructed fairly easily with 63 nodes and 126 edges; are there any four-regular matchstick graphs with less than 63 nodes that can can be constructed (with compass and straightedge) at all?

  • 3
    $\begingroup$ Just a small note: The Haborth Graph is the smallest known graph of this type. It is not known whether or not it is optimal. $\endgroup$ – KSmarts Jan 30 '15 at 21:43
  • $\begingroup$ @KSmarts: I would think if something smaller existed it would have been found, though I guess that may only be true if the smallest graph has some kind of symmetry. The search space for quarter-graphs is a lot smaller than the search space for non-symmetric graphs (the smallest compass-constructable one I can think (126 edges) of doesn't have four-fold symmetry but can be reflected about three axes 120 degrees apart). $\endgroup$ – supercat Jan 30 '15 at 21:50
  • 1
    $\begingroup$ @supercat math.stackexchange.com/questions/1030934/… $\endgroup$ – ghosts_in_the_code Feb 11 '15 at 9:40
  • 2
    $\begingroup$ @ghosts_in_the_code: I didn't see anything on that Q/A about constructing such an angle with anything even remotely resembling compass and straightedge. One answer mentioned producing an arc of unit length, but I would expect the production of such a thing would be directly analogous to squaring the circle. $\endgroup$ – supercat Feb 11 '15 at 16:00
  • 2
    $\begingroup$ @supercat No. The sine will always be a ratio of two constructed line segment lengths, and constructible numbers are a subset of algebraic numbers. $\endgroup$ – KSmarts Feb 17 '15 at 18:28

60 nodes and 120 edges:

enter image description here
The shape that looks like a square is actually a square. And $\tan 75^{\circ} = 2+\sqrt{3}$.

Slightly better than the easy answer.

  • $\begingroup$ Very nice. Your observation about the tangents of 15/75 degrees being constructable is also appropriate, though I think it's obvious how the shape could be constructed even without that, since the group of three triangles at the bottom is easily constructable, as is the square on top. The fourth vertex of the rombus to the right can easily be constructed given the first three, and from there the next three triangles and square can be constructed. Iterating ten more times yields the completed figure. $\endgroup$ – supercat Sep 12 '15 at 22:18
  • $\begingroup$ @supercat Yes, it's obviously constructable. But without tan 75° you cannot know "Iterating ten more times yields the completed figure". $\endgroup$ – user23013 Sep 12 '15 at 22:58
  • $\begingroup$ Good point, though I think that could also be proven geometrically by the fact that if the base of the first group of triangles is horizontal, the edge of the rightmost triangle will be 30 degrees off vertical. Since the sides of the rhombus are parallel, that would imply that each figure is rotated 30 degrees relative to the preceding one. I wonder if an even further-reduced figure is possible. $\endgroup$ – supercat Sep 12 '15 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.