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?
Answer
60 nodes and 120 edges:
The shape that looks like a square is actually a square. And $\tan 75^{\circ} = 2+\sqrt{3}$.
Slightly better than the easy answer.
No comments:
Post a Comment