In graph theory, a graph is a set of vertices along with a set of edges that each connect exactly two different vertices. As a polyformist, it seems natural for me to ask, can we make interesting sets of polyforms out of them? We usually require polyforms to be connected, and we usually look at sets of all polyforms of size n, for some positive integer n. One obvious possibility would be to use sets of all connected graphs of n vertices. But these quickly grow to unwieldy numbers; additionally, they suffer from the problem that once n hits 5, some graphs are non-planar, or impossible to represent in a plane without crossings. This would restrict any search for elegant figures to use in tiling problems with them.
Alternatively, we could look at sets of connected graphs with n edges, which I will call polyedges. There are no non-planar n-edges until size 9. There are 12 pentaedges, the same as the number of pentominoes, and I hope to show that this is a versitile and interesting set of polyforms.
The 12 pentaedges
(The term polyedges is used in some sources to refer to what are more commonly referred to as polysticks, i. e. connected sets of segments in a (typically square) lattice. However, I have need of a term, and polyedge seems so clearly the right one that I feel justified in repurposing it.)
In making tiling problems for polyedges, we treat them like polysticks, allowing polyedges to meet at a vertex but not allowing edges to overlap between forms. Now, one important problem remains: what graphs should we use as patterns for them to tile? We are unconstrained by geometrical considerations, which in the case of polyominoes, for example, pull us toward making rectangles. But we can still use symmetry. Not only are highly symmetrical graphs particularly elegant, but symmetry can narrow the space of solutions; since polyedges are very flexible, this is probably desirable. It will help that the total number of edges in the set is 60, a number with many factors, which should help in our search for symmetrical patterns.
Here are the pentaedges tiling 4 copies of K6, the complete graph (all vertices are connected) with 6 vertices:
This pattern has a truly dizzying amount of symmetry. Every permutation of the vertices in a complete graph maps the graph to itself. There are 6! = 720 such mappings (or automorphisms) for each K6. Since we can permute all four copies independently, on top of which we can arbitrarily reorder the copies themselves, the full pattern has 7204 · 4! = 6,449,725,440,000 automorphisms.
On the other hand, it’s non-planar, and we might want to tile some planar patterns. One highly symmetrical planar pattern with 60 edges is a pair of icosahedra. I show them squished onto a plane for clarity below, but as graphs they’re still equivalent to the 20-sided dice that role-playing gamers use.
Notice that I used 6 colors to distinguish the pentaedges in the figure above. In fact, I had to, since each of the pentaedges touches each of the others within each icosahedron. We could instead try to minimize the number of colors required.
Problem #22: Tile a pair of icosahedra with the pentaedges using only 3 colors, with no two pentaedges of the same color meeting at a point. (It may help to know that there must be 11 vertices where the degrees of the vertex for each adjoining pentaedge are 2, 2, and 1, 7 where they are 3, 1, and 1, and 3 where they are 3 and 2. This can be obtained by counting the total number of vertices of each type in the 12 pentaedges and setting up a system of equations; I won’t get into the details here, but I’ll put them in a comment.)
The pattern above has 28,800 automorphisms. It’s not the most symmetrical planar pattern possible. A set of 4 pentagonal dipyramids has 3,840,000 automorphisms. After finding the other tilings in this post, I got lazy wanted to let others join in the fun, so I’m leaving the problem to you:
Problem #23: Tile a set of 4 pentagonal dipyramids with the 12 pentaedges.
With polysticks, we often like to forbid solutions from containing points where two polysticks cross. We can do the same with polyedges, if we set up the pattern properly:
Notice the trick I played with the pentagonal (or 5-cycle) pentaedge at the bottom of the figure, putting the 5-star pentaedge inside it. In the previous problem, we couldn’t tile the icosahedra without any crossings, because one pentaedge contains a 4-cycle, which can only be placed on an icosahedron with an edge connecting two opposite corners, and the pentaedge containing this edge must cross the 4-cycle. Can we find a pattern where the pentaedges containing 4- and 5-cycles can both enclose one or more other pentaedges, so that the pattern contains only triangular faces and can still be tiled without crossings? Here’s a candidate that can be inscribed on a cube; in this case it seems clearer to show the cube in an unfolded state than to squish it as we did with the icosahedra.
Problem #24: Tile the above figure with the pentaedges. (Keep in mind that in the unfolded version, the edges that fold together count as a single edge. The pentaedges that are already placed are just for illustration, and can be placed differently in a solution.)
To make it a bit easier to communicate solutions or new problems you find, I’m providing source svgs (made in Inkscape) for some of the images above. They contain copies of the relevant patterns in plain black, which can be turned into a solution by recoloring the edges.
Problem #22 (Icosahedra)
Hexagonal figure
Problem #24 (Cube with triangles)
This post expands on material at my non-blog. Theoretically, I’m using this blog to write more exploratory material in the service of the non-blog, where I intend to collect it in a more digested form. However, lately I’ve been more poaching the non-blog for material to use here, and I haven’t gotten around to updating the non-blog as I mean to. Nevertheless, if you like what you’ve been seeing here, you should check it out, as it contains most of my polyform discoveries from the ’00s.
