Dodecahedral Graph

The dodecahedral graph is the Platonic graph corresponding to the connectivity of the vertices of a dodecahedron, illustrated above in four drawings. The left drawing shows a stereographic projection of the dodecahedron, the second an orthographic projection, the third is from Read and Wilson (1998, p. 162), and the fourth is derived from LCF notation.

The dodecahedral graph is the skeleton of the great stellated dodecahedron as well as the dodecahedron.

It is the cubic symmetric graph denoted and is isomorphic to the generalized Petersen graph . It can be described in LCF notation as [10, 7, 4, , , 10, , 7, , .

The dodecahedral graph is implemented in the Wolfram Language as GraphData["DodecahedralGraph"].

It is distance-regular with intersection array and is also distance-transitive. It is also its own distance-4 graph distance graph.

It is also a unit-distance graph (Gerbracht 2008), as shown above in a unit-distance embedding.

Finding a Hamiltonian cycle on this graph is known as the icosian game. The dodecahedral graph is not Hamilton-connected and is the only known example of a vertex-transitive Hamiltonian graph (other than cycle graphs ) that is not H^*-connected (S. Wagon, pers. comm., May 20, 2013).

The dodecahedral graph has 20 nodes, 30 edges, vertex connectivity 3, edge connectivity 3, graph diameter 5, graph radius 5, and girth 5. It has chromatic number 3. Its graph spectrum is (Buekenhout and Parker 1998; Cvetkovic et al. 1998, p. 308). Its automorphism group is of group order (Buekenhout and Parker 1998).

The minimal planar integral drawing of the dodecahedral graph has maximum edge length of 2 (Harborth et al. 1987). It is also graceful (Gardner 1983, pp. 158 and 163-164; Gallian 2018, p. 35; Knuth 2025) with 784,298,856 fundamentally different graceful labelings, giving a total number of graceful labelings (B. Dobbelaere, pers. comm., Oct. 22, 2020), a number independently (and nearly simultaneously!) determined by T. Rokicki on Oct. 6, 2020 (D. Knuth, pers. comm., Jul. 6, 2023).

The dodecahedral graph can be constructed as the graph expansion of with steps 1 and 2, where is a path graph (Biggs 1993, p. 119).

The skeleton of the great stellated dodecahedron is isomorphic to the dodecahedral graph.

The line graph of the dodecahedral graph is the icosidodecahedral graph. The graph square of the dodecahedral graph is its crossed graph.

The dodecahedral graph has chromatic polynomial

The plots above show the adjacency matrices, incidence matrices, and graph distance matrices for the dodecahedral graph.

The bipartite double graph of the dodecahedral graph is the cubic symmetric graph .

The following table summarizes properties of the dodecahedral graph.

property	value
automorphism group order	120
characteristic polynomial
chromatic number	3
chromatic polynomial
claw-free	no
clique number	2
determined by spectrum	yes
diameter	5
distance-regular graph	yes
dual graph name	icosahedral graph
edge chromatic number	3
edge connectivity	3
edge count	30
Eulerian	no
generalized Petersen graph indices
girth	5
Hamiltonian	yes
Hamiltonian cycle count	60
Hamiltonian path count	?
integral graph	no
independence number	8
LCF notation
line graph	?
line graph name	icosidodecahedral graph
perfect matching graph	no
planar	yes
polyhedral graph	yes
polyhedron drawing names	dodecahedron, great stellated dodecahedron
radius	5
regular	yes
spectrum
square-free	yes
traceable	yes
triangle-free	yes
vertex connectivity	3
vertex count	20
weakly regular graph parameters