Building graphs with integersticks and bad matchsticks

For a long time I’ve enjoyed reading about matchstick graphs, and lately I’ve been thinking of some more general planar straight-line graphs to play with.

A matchstick graph (to paraphrase a bunch of definitions) is one you can draw, in a plane, by connecting nodes with edges that are all the same length, without any of the edges crossing or being superimposed on one another, and so that the graph is a single connected component. Or, put more pragmatically, if you have a big pile of finely-made wooden matches (all absolutely 100% accurately the same length), you make a matchstick graph by superimposing their ends on one another. So obviously you can make a long wobbly end-to-end chain of them, or a big wobbly polygon which is just a wobbly line that’s closed back on itself, or a star where all the matches overlap at one end, or you can make some triangles, or some squares, or some flexible parallelogram things. And you can make bigger graphs out of those components… as long as the constraints of not overlapping don’t get in your way.

Those constraints are interesting, in the same way the domino constraints I’ve been exploring elsewhere are interesting. They make the larger-graph layout question a bit more complicated than you might imagine, in what feels a lot like the way the domino-tiling problem for arbitrary regions is more complicated than you might imagine. They make things like the Harborth Graph interesting.

One of the interesting directions, in case you’re not arranging and flexing and pivoting matchsticks on a tabletop already, is that they are related to mechanical straight-line linkages. That is, if you have a match that’s only attached to another at one end, it can swirl around quite a bit… bit not into a position where it bumps into or overlaps another match. Or a square arrangement of four matches (with no diagonal, because if there was a match on a diagonal it wouldn’t be square now would it?) can squish into a diamond shape and almost but not quite down to a straight line because then two matches would have to overlap one another.

Actually think about that one for a second, before I go on. Imagine you arranged four matches in a rough square. As you squish the square down into a diamond shape, you bring two of the edges closer together—probably while saying “squish” out loud to yourself—you are also pushing the other two vertices farther apart from one another. If that square is in a bigger layout, then those corners will have to accommodate the movement. Which is how you get things like robot legs (if you want that) or ensure your bridge doesn’t fall down if that’s your plan. So they’re interesting for doing stuff.

Anyway, matchstick graphs. Play with some matches and it gets fun. I’m still looking for some software that will help me draw some, so you don’t get any from me today.

Instead….

What if instead of a collection of matches of identical length, I gave you a collection of integersticks? In a set of integersticks, you have exactly one stick of each integer length. That is, one stick each of lengths \(\{1,2,3,\dots\infty\}\).

What can you make of those, if you follow the rules we used for matchstick graphs?

Later: Ron points out that if you have an infinite collection of integer-length sticks, you can just reach over towards the right end of the collection sorted by size and pick up as many infinitesimally-different ones as you want, and do everything that you can do with matchsticks. So let me drop the additional rule here that I didn’t realize I’d forgotten to mention. That is: You can’t skip sticks. If you use \(N\) sticks in total in your construction, they must be of lengths \(\{1,2,3,\dots,N\}\), not some other lengths. My mistake leaving that out.

One interesting thing, at least to me, is that now—possibly because the sticks differ in a real way from one another—you have to pay attention to which is which. You can build some triangles, but not all of them, for instance: you can build a triangular structure from \(\{3,4,5\}\) but not \(\{1,2,3\}\) (because it’s flat) or \(\{1,2,91\}\) (because trust me, I promise you can’t).

Where before, with identical matchsticks, we could build a polygon of arbitrary size, now with integersticks we have some troubles and new constraints, don’t we? We can still build an arbitrary star, or open chain, but not an arbitrary polygon (see \(\{1,2,91\}\) above for a trivial example of “no”).

So what can you build?

Let’s look at the matchstick graph example for some leads. Can you build any regular graphs? Yes: any of the polygons that are permitted by the length constraints. Can you build a 3-regular graph? Can you build (as did Harborth) a 4-regular graph?

What if we relax the constraint of not-crossing (but not the constraint of not being superimposed)? Does that permit linkages that were not previously permitted?

What if I said you could use two sets of integersticks? What’s easier now?

And finally, there’s a related notion: bad matchsticks.

This is breaking the rules for matchstick graphs in a different direction: Suppose instead of being of absolutely accurate one-unit matches, or absolutely accurate integer-length sticks, you were given a box of matches each of which was slightly (and unpredictably) different in length from the others. Let’s say that each match was of different length, within some \(\epsilon\) of one unit.

Say I ask you to build a Harborth graph, or some other matchstick graph, using the bad matches instead of the ideal good ones? How small must \(\epsilon\) be, for you to be able to construct the graph?

This is about tolerances, I guess, huh?

I think I should go find a way of drawing these things. Maybe you can, too.