April 10th, 2011 by munizao Leave a reply »

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.


  1. munizao says:

    Proof of the statement above on the partitions of vertices in a double icosahedron 3-coloring:

    Keep in mind that there are 24 vertices, all of degree 5. The following are all of the partitions of 5 with 3 or fewer parts:

    The pentaedges contain the following number of vertices of each degree:
    5: 1
    4: 2
    3: 10
    2: 25
    1: 27

    The 5 and 4 degree vertices have only one possible partition where they can fit, so we can pull them out, leaving:

    3: 10
    2: 25
    1: 25

    and 21 total vertices.

    Now we can set up some equations:

    a) |3,2| + |3,1,1| = 10
    b) |3,2| + 2·|2,2,1| = 25
    c) 2·|3,1,1| + |2,2,1| = 25
    d) |3,2| + |3,1,1| + |2,2,1| = 21

    Then |2,1,1| = 11 (by subtracting a from d,)
    |3,2| = 3 (by substituting in b,)
    and |3,1,1| = 7 (by substituting in a or c.)

  2. Bryce Herdt says:

    In the 4K6 problem, I’d be satisfied if the pentaedges didn’t self-cross. And sadly, the current distribution doesn’t allow that.

    Lemma: The five edges making up the pentagram must be occupied by all three pentaedges, with consecutive groups of 1, 2, and 2 edges in some order.
    A check of which of a pentagram’s edges cross is enough to show this.

    Now, the second K6 contains both a red loop and a blue snake (a list of standardized names would be helpful). Neither of these can take up two edges of the pentagram, so they must appear separately, Q.E.D.

    Not sure whether it’s possible. The asterisk (first K6, red) is one pentaedge that must take two legs of the pentagram, but my mind’s just going to wander off now.

  3. munizao says:

    One way would be to switch the embedding. I mostly picked this embedding to show off the symmetry of the pentagon and the 5-star. Sadly, the only embedding of K6 with more symmetry (vertices at the corners of a regular hexagon) won’t work. There is a triplet of edges cutting the hexagon in half; each edge in the triplet must be in a different pentaedge. But the pentagon cannot be formed with such an edge without crossing itself.

    One embedding with a little less symmetry that might work is a pair of concentric equilateral triangles with the same orientation. (Equivalently, a triangular prism including the diagonals of the rectangles.) This only has three crossings! That might be too easy though, so you might be able to add an extra constraint, like having all three pairs of pentaedges represented in the three crossings.

  4. me says:

    did you hear this problem?
    we have a graph with 6 vertices,we can prove that there is a k3 in this graph or there is a k3 in complement of this graph.

    what can we say about a graph with 8 vertices? is this sentence true?:

    we have a graph with 8 vertices,we can prove that there is a k4 in this graph or there is a k4 in complement of this graph.

  5. munizao says:

    me: (who is not me) This appears to be a classic problem in Ramsay theory. According to this reference, 18 vertices are needed to force the presence of a k4 subgraph in a graph or its complement.

    I’m not sure whether this applies usefully to designing polyedge tiling puzzles, though.

  6. Bryce Herdt says:

    Here’s a counterexample, “me”: arrange the vertices to form a regular octagon, then take the graph formed by the octagon’s sides and diameters.
    In this graph, each vertex has just three edges, all of which would be needed in a K4, but the three vertices on the other ends of those edges only connect in the complement.
    In the complement, each vertex is connected to four others; measured from the center, two vertices are 90 degrees away and the other two are 135 degrees away. But however we choose three of these four vertices, two will be 45 degrees from each other and only share an edge in the original graph.

Leave a Reply