Octahedral Graph


"The" octahedral graph is the 6-node 12-edge Platonic graph having the connectivity of the octahedron. It is isomorphic to the circulant graph Ci_6(1,2), the cocktail party graph K_(3×2), the complete tripartite graph K_(2,2,2), and the 4-dipyramidal graph. Several embeddings of this graph are illustrated above.

It is implemented in the Wolfram Language as GraphData["OctahedralGraph"].

The octahedral graph has 6 nodes, 12 edges, vertex connectivity 4, edge connectivity 4, graph diameter 2, graph radius 2, and girth 3. It is the unique 6-node quartic graph, and is also a quartic symmetric graph. It has chromatic polynomial


and chromatic number 3. It is an integral graph with graph spectrum Spec(G)=(-2)^20^34^1. Its automorphism group is of order |Aut(G)|=48.

The octahedral graph is the line graph of the tetrahedral graph.


There are three minimal integral embeddings of the octahedral graph, illustrated above, all with maximum edge length of 7 (Harborth and Möller 1994).


The minimal planar integral embeddings of the octahedral graph, illustrated above, has maximum edge length of 13 (Harborth et al. 1987). The octahedral graph is also graceful (Gardner 1983, pp. 158 and 163-164).


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

The following table summarizes some properties of the octahedral graph.

automorphism group order48
characteristic polynomial(x-4)x^3(x+2)^2
chromatic number3
chromatic polynomial(x-2)(x-1)x(x^3-9x^2+29x-32)
circulant graphCi_6(1,2)
clique number3
graph complement name3-ladder rung graph
determined by spectrumyes
distance-regular graphyes
dual graph namecubical graph
edge chromatic number4
edge connectivity4
edge count12
Hamiltonian cycle count32
Hamiltonian path count240
integral graphyes
independence number2
line graphyes
perfect matching graphno
polyhedral graphyes
polyhedron embedding namesoctahedron, tetrahemihexahedron
strongly regular parameters(6,4,2,4)
vertex connectivity4
vertex count6

Confusingly, the term "octahedral graph" is also used to refer to a polyhedral graph on eight nodes. There are 257 topologically distinct octahedral graphs, as first enumerated by Kirkman (1862-1863) and Hermes (1899ab, 1900, 1901; Federico 1969; Duijvestijn and Federico 1981). The cubical graph is an octahedral graph.

See also

Circulant Graph, Cubical Graph, Dipyramidal Graph, Dodecahedral Graph, Icosahedral Graph, Integral Graph, Octahedron, Platonic Graph, Polyhedral Graph, Quartic Graph, Quartic Symmetric Graph, Tetrahedral Graph

Explore with Wolfram|Alpha


Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 234, "Octahedron =J(4,2).", A. J. W. and Federico, P. J. "The Number of Polyhedral (3-Connected Planar) Graphs." Math. Comput. 37, 523-532, 1981.Federico, P. J. "Enumeration of Polyhedra: The Number of 9-Hedra." J. Combin. Th. 7, 155-161, 1969.Gardner, M. "Golomb's Graceful Graphs." Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.Grünbaum, B. Convex Polytopes. New York: Wiley, pp. 288 and 424, 1967.Harborth, H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.Harborth, H.; Kemnitz, A.; Möller, M.; and Süssenbach, A. "Ganzzahlige planare Darstellungen der platonischen Körper." Elem. Math. 42, 118-122, 1987.Hermes, O. "Die Formen der Vielflache. I." J. reine angew. Math. 120, 27-59, 1899a.Hermes, O. "Die Formen der Vielflache. II." J. reine angew. Math. 120, 305-353, 1899b.Hermes, O. "Die Formen der Vielflache. III." J. reine angew. Math. 122, 124-154, 1900.Hermes, O. "Die Formen der Vielflache. IV." J. reine angew. Math. 123, 312-342, 1901.Kirkman, T. P. "Application of the Theory of the Polyhedra to the Enumeration and Registration of Results." Proc. Roy. Soc. London 12, 341-380, 1862-1863.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 266, 1998.

Cite this as:

Weisstein, Eric W. "Octahedral Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications