# Touching Matchsticks

You are asked to place matchsticks on a flat surface such that each matchstick end meets three others, and no matches cross. It is easy to achieve this for patterns that extend indefintely: The challenge is to truncate such patterns to finite 2D networks. How small a matchstick network can you create?

Further clarifications: the matchsticks all have equal length and can be thought of as mathematical line segments. At each point of contact, exactly four ends meet. All matches lay flat on the surface, no gluing allowed!

• A match can touch 3 or more other matches, right? – Spikatrix Jan 28 '15 at 14:08
• At each point where matches are in contact, exactly 4 matches meet. Have sharpened the puzzle text to clarify this point. Thanks. – Johannes Jan 28 '15 at 15:07
• Do you know if there even is a solution? – Ivo Beckers Jan 28 '15 at 15:09
• Yes, a solutions exists. – Johannes Jan 28 '15 at 15:14

I must admit that I found It with google but this is the solution: • Is there any logical means to finding it, or just hit and trial? – ghosts_in_the_code Jan 28 '15 at 15:19
• I figured that what we want is actual called a "4-regular graph" and that is the exact term I google image searched – Ivo Beckers Jan 28 '15 at 15:21
• @ghosts_in_the_code - here is some explanation on the construction of this 4-regular matchstick graph: geometryexpressions.com/… – Johannes Jan 28 '15 at 15:38
• Is there any proof of this being the smallest possible? – user2813274 Jan 28 '15 at 19:13
• @user2813274 - whether or not 104 matches is the minimum is an open problem. – Johannes Jan 29 '15 at 13:09

An arrangement which can be readily seen to be valid albeit not minimal may be formed by observing that joining two "small" (3-matchstick) triangles and two "large" (9-matchstick) rigid triangles will yield a construct with four vertices of order two (the remaining vertices are all of order four). The order-two vertices will form a trapezoid whose non-parallel edges are of equal length and form an angle which may, by flexing the joints, may be adjusted within a range that includes 45 degrees and extends almost up to 60. One may thus fasten seven or eight such constructs together to yield a "donut" which meets the necessary conditions. The figure on the left has the angles adjusted so as to show that the range extends slightly beyond 45 degrees. Other constructs may use fewer line segments, but this construct is probably the "simplest".

Another useful building block is this combination of four large and two small triangles: While this section, unlike the one above, isn't directly flexible, it only has two order-two nodes rather than four. As a consequence, three of them may be combined to yield a regular graph, or--more interestingly--four of them may be combined to yield a flexible regular graph.

• +1 Nice symmetric construct. This repeat unit can also be utilized to demonstrate infinitely many solutions exist. – Johannes Jan 29 '15 at 2:18
• @Johannes: I'd been wondering for awhile whether it was possible to have a "flexible" regular graph; I finally came up with the answer. – supercat Jan 29 '15 at 4:59

Here is a more symmetrical solution, not minimal though.

PS: That solution was also given there: Touching matchsticks with compass and straightedge