Dodecahedron spanning trees (JMM 2025)
Dodecahedron spanning trees (JMM 2025)
Embedded Files
A dodecahedron is a polyhedron that consists of twelve regular pentagons that have been glued together to that at every corner three pentagons meet. This is one of the five Platonic solids and is widely used to make twelve-sided die that are used for some games.
This particular construction is more aptly building the skeleton of the dodecahedron using two types of LEGO pieces. There are twenty of the 3-branch cross axle (57585) acts as vertices and thirty of the Angle element, 135 degree (42156) acts as the edges.
On a technical side-note this is a slightly illegal LEGO build. That is to say, what we are properly building is the dual of the icosahedron. For an icosahedron the dihedral angle between two faces is 138.19... degrees while the pieces that we are using have 135 degrees. But what is 3 degrees between friends.
Local structure at a vertex; continue expanding on this and the dodecahedron builds itself
A finished model
A tutorial video which gives a walkthrough on how to build the model
The dodecahedron graph is formed by letting each corner be a vertex and each edge be, well an edge. So in particular what we have really formed is a 3D-realization of the dodecahedron graph. One widely studied aspect of graphs are the (minimal) spanning trees. By spanning we mean that we can travel along the (in our case blue) edges and get from any vertex to any other vertex; by a tree this means there are no superfluous edges, in other words the blue edges have no loops, equivalently this is being done with as few edges as possible.
As long as a graph is connected there will be a spanning tree and there are several algorithms to find some. So we know there are spanning trees for the dodecahedron graph, but how many? This depends on what we want to count as being distinct. So here are some possible answers:
5,184,000 -- This is the number of labeled spanning trees of the dodecahedron. This is what is found by using Kirchoff's Matrix-Tree Theorem.
16,861 -- This is the number of non-isomorphic trees which exist as some spanning tree of the dodecahedron
43,380 -- This is the number of spanning trees of the dodecahedron up to full symmetry of the dodecahedron. In other words, every spanning tree is equivalent to one of these under the operation of rotation / mirroring.
86,760 -- This is the number of spanning trees of the dodecahedron up to rotation of the dodecahedron. In other words, every spanning tree is equivalent to one of these under rotating the dodecahedron in your hand, but mirroring is not allowed.
The astute observer might notice that the last two numbers are highly similar, and that leads to the following.
Fact: For any spanning tree of the dodecahedron if you take the mirror image, then no subsequent rotation will get you back to the spanning tree that you started with.
It also should be noted that not every tree occurs equally often as a spanning tree. For instance the path has 18 different ways to be embedded into the dodecahedron (shown below); but that doesn't even crack the top twenty-five in terms of number of distinct embeddings. There is one tree which has 30 different embeddings as a spanning tree of the dodecahedron! On the other end there are 6,748 trees which have a unique embedding as a spanning tree of the dodecahedron.
The 18 different ways to imbed the path into the dodecahedron (36 if you count mirror symmetries as distinct).
The 18 different ways to imbed the path into the dodecahedron (36 if you count mirror symmetries as distinct).
mathreu.org
Iowa State Math REU running in 2025 with projects in combinatorics.
mathgrad.org
Iowa State graduate program in Applied Math or (pure) Math.
A debt-free PhD!
mathpostbac.org
One-year program at Iowa State to help prepare students for PhD programs in Applied Math or (pure) Math.
Google Sites
Report abuse