**Spanning Trees of the Cube and Their Associated Nets**

prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

__malkevitch@york.cuny.edu__

web page:

__http://york.cuny.edu/~malk/__

If P is a convex 3-dimensional polyhedron, then can one cut along the edges of a spanning tree of P and flatten out the faces of P so that they form a simple plane polygon? The question of whether or not, by cutting the edges of a convex polyhedron, its faces can be flattened without overlap was first raised explicitly by the English geometer Geoffrey Shephard. The question remains unanswered to this day! The polygons that are obtained in this way are typically called *nets*. However, note that given a polygon N in the plane that was obtained from P as a net, it may be possible to fold N in a way that pastes the edges of N together so that a polyhedron P* not isomorphic to P is obtained! This fact was already noted by Shephard.

Many facts are known about nets but here I wish to raise some issues that put together some known facts but perhaps in a novel way. The investigations raised here concern the 11 nets of a 1x1x1 cube, which as a polyhedron is known to have 48 symmetries (isometries). The rotation group has order 24 but the full group of isometries has order 48. The graph associated with the vertices and edges of the cube has automorphism group of order 48. Thus, there are as many "symmetries" of the graph of a cube (a combinatorial object) as there are for the metrically regular cube. Each of the 11 nets thought of as a polygon also has symmetries.

The "regular" 3-cube has 11 nets. Note that there are convex polyhedra which are combinatorially equivalent to the 3-cube, that is, their graphs have the same graph as that of the 3-cube but are not metrically equivalent to the 3-cube. Examples include a 1x1xk (k a positive integer not 1) brick and a square pyramid with equilateral triangles (base a square; 4 equilateral triangles meeting at the apex) where the apex has been truncated by a plane that is parallel to the square base, creating a square face with 1/2 the edge length of the base. This truncated square pyramid has many more than 11 nets.

**Investigation 1**

One collection of interesting questions is to determine exactly the number of nets of different solids which are combinatorially equivalent to the cube and try to relate the number of nets to the reduced symmetry of the polyhedra one is dealing with.

Cases to look at:

a. 1x1xk (k at least 2) bricks

b. Square pyramid with equilateral triangle faces truncated with a plane parallel to the base so that the "top" face is a square 1/2 the edge length of the base

c. Square pyramid with equilateral triangle faces truncated with planes parallel to the base at different heights

d. A shaved cube (see Figure 1) This polyhedron has two congruent square faces, two congruent trapezoidal faces, and two rectangular faces which are not congruent to each other.

Figure 1

Note: There are many other cases to consider before reaching the situation where there are 6 non-congruent "irregular quadrilaterals" for faces!

Now return to the regular metrical cube situation.

Observation 1: If one has any of the 11 nets of the cube, one can designate one of the six faces of the cube as B and fold the cube up so that face B is the face on which the cube rests after the folding!

The next exploration I have in mind concerns the relation between:

a. The spanning trees of the cube

Note that two spanning trees of a graph will be considered "different" if they use different edges. However, notice that different spanning trees may be isomorphic. For example, the graph which is a five cycle (5 edges and 5 vertices) has 5 different spanning trees (a different tree arises for each different edge of the cycle that is omitted) but all of these 5 spanning trees are isomorphic to each other. The different spanning trees are all paths with 4 edges.

b. The specific spanning trees of the cube in a fixed position that give rise to a net with a particular face as its bottom face indicated

c. The symmetry of the net

d. The symmetry of the spanning tree

e. The isomorphism class of the tree involved (those that give rise to nets)

First recall that a (regular) cube (all faces congruent squares) can be represented in a variety of ways on a flat piece of paper. Here we will be concerned with "isometric" drawings, graph drawings, and nets. Furthermore, we can imagine a standard version of the isometric drawing which we will label in the same way.

Figure 2

In Figure 3 below, a different "bottom" square B has been designated in the net for the folded cube to sit on. This means that for the same net we can cut along the edges of a different spanning tree.

Figure 3

Investigation 2

There are a total of 384 spanning trees of a 3-cube. This number is the same for all the different metrical realizations of the 3-cube and can be computed by using the Matrix Tree Theorem, which is implicit in work of Gustav Kirchhoff. (The theorem involves the computation of a determinant of a matrix which can be obtained from the adjacency matrix of the graph and the degrees of the vertices of the graph. A proof of this theorem requires knowledge of linear algebra.) There are several different isomorphism classes for trees with 7 edges and 8 vertices that are associated with nets.

a. Draw all the non-isomorphic trees that have 8 vertices. (Hint: There are 23.) How many of these have maximal valence 3? (To be a spanning tree of a 3-cube the maximal valence must be three.) Show that not all trees of maximal valence 3 with 8 vertices can be spanning trees of a 3-cube.

b. How are the different types of spanning trees related to the 11 nets? Is the symmetry of the tree related to the symmetry of the net in any ways?

c. For each choice of net and choice of face for the folded net to rest on, which labeled tree of the cube arises? How are these trees that arise from the 11 nets of the cube related to the 384 different trees of the cube and the 48 symmetries of the cube?

References:

Chartrand, G. and P. Zhang, Introduction to Graph Theory, McGraw Hill, New York, 2005.

Merris, R. Graph Theory, Wiley, New York, 2001.

West, D. Introduction to Graph Theory, (Second edition), Upper Saddle River, 2001.