# Touching matchsticks with compass and straightedge

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. 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?

• 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. – KSmarts Jan 30 '15 at 21:43
• @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). – supercat Jan 30 '15 at 21:50
• – ghosts_in_the_code Feb 11 '15 at 9:40
• @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. – supercat Feb 11 '15 at 16:00
• @supercat No. The sine will always be a ratio of two constructed line segment lengths, and constructible numbers are a subset of algebraic numbers. – KSmarts Feb 17 '15 at 18:28 The shape that looks like a square is actually a square. And $\tan 75^{\circ} = 2+\sqrt{3}$.