Unfolding the Tesseract

Detail from an image by Mark McClure

Unfolding the Tesseract

Journal of Recreational Mathematics, Vol. 17(1), 1984-85

Introduction

In 1966, Martin Gardner asked, “How many different order-8 polycubes can be produced by unfolding a hollow hypercube into 3-space?” [1], stating also that he did not know the answer. There are 261 distinct unfoldings and in this article I will show how I arrived at that number.

The method given for enumerating unfolded tesseracts can be extended to any number of dimensions. I'll first demonstrate the method on the cube, and then on the tesseract.

The Cube

A tree is a connected graph with n nodes and n - 1 edges. Figure 1 shows the six six-node trees [2]. We may arrange the six nodes of a tree into three pairs and specify that the members of a pair may not be adjacent. Let us call such a tree a “paired tree”. Thus, a paired tree is a tree together with a perfect matching in its complement.

Figure 1. The six six-node trees

There are eleven distinct pairings of the six-node trees. There are also eleven unfolded cubes. There is a one-to-one mapping from the set of unfolded cubes to the set of paired six-node trees. The mapping is shown in Figure 2.

Figure 2. Mapping between unfolded cubes and paired six-node trees.

There is a simple procedure for finding the unique paired tree that an unfolded cube maps to.

Pair the squares of an unfolded cube if the squares become opposite faces on folding. A cube has three pairs of opposite faces.
Replace the squares with points.
Connect two points if the squares they replaced were adjacent.

An example is shown in Figure 3.

Figure 3. Procedure for mapping an unfolded cube to a paired tree.

This procedure will always produce a tree because the six squares of an unfolded cube will always be connected along five lines. If there were fewer than five connections, the six squares would not all be joined into a unit. If there were more than five connections, the unfolded cube could not lie on a plane. For similar reasons, a six-node tree must have five edges. If a six-node graph has less than five edges, the six nodes will not all be joined into a unit. If a six-node graph has more than five edges, there will be a cycle in it.

This procedure will never pair adjacent nodes in a tree because opposite faces of a cube are never adjacent. No unfolding of a cube can make opposite squares adjacent

Finally, it is clear that this procedure will always produce a unique paired tree. An unfolded cube maps to only one tree and uniquely describes the pairing of the nodes of the tree.

Let us consider the inverse of this procedure. The inverse procedure finds the unique unfolded cube that a paired six-node tree maps to.

Consider a cube. Number all the vertices and cut the cube apart into six squares. You should have something like that shown in Figure 4.

Figure 4. Six squares with numbered vertices.

Since we cannot cut a tesseract apart, let us look for a way to characterize this numbering. The simplest method is graphic, as shown in Figure 5. We may arrange these numbered squares into pairs of opposites as shown in Figure 6.

Figure 5. Cutting and numbering a projected cube.

Figure 6. Three pairs of opposing squares.

We now give the procedure for finding the unique unfolded cube that any paired six-node tree maps to.

Replace each node of the tree with one of the above numbered squares, the only restriction being that paired nodes must be replaced by paired squares.
Connect two squares if the nodes they replaced were adjacent, the only restriction being that squares must be connected so that their numbers match. Note that some squares may be upside-down, and it is permitted to turn them over.
Now, remove the numbers.

An example is shown in Figure 7.

Figure 7. Procedure for mapping a paired tree to an unfolded cube.

It will always be possible to connect the squares so that their numbers match. Inspection of the above numbered squares will show that any two squares can be connected, so long as they are not both members of the same pair. Thus, there is a one-to-one mapping from the set of unfolded cubes to the set of paired six-node trees. The procedures given here can be generalized to any number of dimensions. Now let us consider the unfolding of the tesseract into 3-space.

The Tesseract

A tesseract projected onto two dimensions is shown in Figure 8.

Figure 8. A tesseract projected onto two dimensions.

A hollow tesseract is made up of eight solid cubes, just as a hollow cube is made up of six solid squares. The eight cubes may be put into four pairs of opposite cubes, just as the six squares of a cube may be put into three pairs of opposite squares.

There is a one-to-one mapping from the set of unfolded tesseracts to the set of paired eight-node trees. An example is shown in Figure 9.

Figure 9. Example of mapping between unfolded tesseracts and paired eight-node trees.

There are twenty-three eight-node trees, as shown in Figure 10 [2].

Figure 10. The twenty-three eight-node trees.

The 261 pairings of the eight-node trees are shown in Figures 11.1 through 11.24.

Figure 11.1. Pairings of the 1st eight-node tree.

Figure 11.2. Pairings of the 2nd eight-node tree.

Figure 11.3. Pairings of the 3rd eight-node tree.

Figure 11.4. Pairings of the 4th eight-node tree.

Figure 11.5. Pairings of the 5th eight-node tree.

Figure 11.6. Pairings of the 6th eight-node tree.

Figure 11.7. Pairings of the 7th eight-node tree.

Figure 11.8. Pairings of the 8th eight-node tree.

Figure 11.9. Pairings of the 9th eight-node tree.

Figure 11.10. Pairings of the 10th eight-node tree.

Figure 11.11. Pairings of the 11th eight-node tree.

Figure 11.12. Pairings of the 12th eight-node tree.

Figure 11.13. Pairings of the 13th eight-node tree.

Figure 11.14. Pairings of the 14th eight-node tree.

Figure 11.15. Pairings of the 15th eight-node tree.

Figure 11.16. Pairings of the 16th eight-node tree.

Figure 11.17. Pairings of the 17th eight-node tree.

Figure 11.18. Pairings of the 18th eight-node tree.

Figure 11.19. Pairings of the 19th eight-node tree.

Figure 11.20. Pairings of the 20th eight-node tree.

Figure 11.21. Pairings of the 21st eight-node tree.

Figure 11.22. Pairings of the 22nd eight-node tree.

Figure 11.23. Pairings of the 23rd eight-node tree.

Figure 11.24. Number of pairings of all eight-node trees.

As far as I know, the only way to find the number of distinct pairings a tree can have is to exhaustively examine the possibilities. That is what I have done here.

Note that there are some pairings of a tree which look distinct, but are actually identical. We may have two or more different representations of the same paired tree. Consider the example shown in Figure 12.

Figure 12. Two representations of the same paired tree.

Conclusion

There are 261 ways of pairing the eight-node trees. Thus, there are 261 unfolded tesseracts.

There are 106 ten-node trees [2]. I have not determined how many ways they can be paired. An exhaustive examination of the possibilities will probably require a significant amount of computer time.

Figure 13 shows the two four-node trees and Figure 14 shows the only way of pairing them. Thus, there is only one way of unfolding a square (Figure 15).

Figure 13. The two four-node trees.

Figure 14. The only pairing of the four-node trees.

Figure 15. The only unfolding of a square.

There is only one two-node tree, which cannot be paired (Figure 16).

Figure 16. The only two-node tree.

This gives us an infinite sequence: 1,11, 261, .... As far as I know, this is a new sequence.

Acknowledgements

Thanks to Martin Gardner of Scientific American for posing the problem, Norman Johnson of Wheaton College for encouragement, D.G. Corneil and E. Mendelsohn of the University of Toronto for assistance, and the University of Toronto for computer time.

References

M. Gardner, Mathematical Games, Scientific American, 214:5, pp. 138-143, November 1966.
F. Harary and G. Prins, The Number of Homeomorphically Irreducible Trees and Other Species, Acta Mathematica, 101. pp. 141-162, 1959.

A Brief Tutorial by Davide Cervone