"The" octahedral graph is the 6-node 12-edge Platonic graph having the connectivity of the octahedron.
It is isomorphic to the circulant graph 
, the cocktail party
graph 
,
the complete tripartite graph 
, 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 
. Its automorphism
group is of order 
.
The octahedral graph is the line graph of the tetrahedral graph. It is also the graph square of the cycle 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.
| property | value |
| automorphism group order | 48 |
| characteristic polynomial |  |
| chromatic number | 3 |
| chromatic polynomial |  |
| circulant graph |  |
| claw-free | yes |
| clique number | 3 |
| graph complement name | 3-ladder rung graph |
| determined by spectrum | yes |
| diameter | 2 |
| distance-regular graph | yes |
| dual graph name | cubical graph |
| edge chromatic number | 4 |
| edge connectivity | 4 |
| edge count | 12 |
| Eulerian | yes |
| girth | 3 |
| Hamiltonian | yes |
| Hamiltonian cycle count | 32 |
| Hamiltonian path count | 240 |
| integral graph | yes |
| independence number | 2 |
| line graph | yes |
| perfect matching graph | no |
| planar | yes |
| polyhedral graph | yes |
| polyhedron embedding names | octahedron, tetrahemihexahedron |
| radius | 2 |
| regular | yes |
| spectrum |  |
| square-free | no |
| strongly regular parameters |  |
| traceable | yes |
| triangle-free | no |
| vertex connectivity | 4 |
| vertex count | 6 |
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.
."