# 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? Commented Jan 28, 2015 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. Commented Jan 28, 2015 at 15:07
• Do you know if there even is a solution?
– Ivo
Commented Jan 28, 2015 at 15:09
• Yes, a solutions exists. Commented Jan 28, 2015 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? Commented Jan 28, 2015 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
Commented Jan 28, 2015 at 15:21
• @ghosts_in_the_code - here is some explanation on the construction of this 4-regular matchstick graph: geometryexpressions.com/… Commented Jan 28, 2015 at 15:38
• Is there any proof of this being the smallest possible? Commented Jan 28, 2015 at 19:13
• @user2813274 - whether or not 104 matches is the minimum is an open problem. Commented Jan 29, 2015 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. Commented Jan 29, 2015 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. Commented Jan 29, 2015 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