15
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 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, 2015 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, 2015 at 21:50
  • 1
    $\begingroup$ @supercat math.stackexchange.com/questions/1030934/… $\endgroup$
    – ghosts_in_the_code
    Feb 11, 2015 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, 2015 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, 2015 at 18:28

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2015 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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