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 , the cocktail party graph , the complete tripartite graph , and the 4-dipyramidal graph. Several drawings 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 group 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 drawings of the octahedral graph, illustrated above, all with maximum edge length of 7 (Harborth and Möller 1994).

The minimal planar integral drawing 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 matrix, incidence matrix, and graph distance matrix 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
graph spectrum
square-free	no
strongly regular parameters
traceable	yes
triangle-free	no
vertex connectivity	4
vertex count	6

The term "octahedral graph" is also used for a polyhedral 8-vertex graph (Gayathri 2018, p. 50). A further convention uses -octahedral graph for the cocktail party graph on vertices (Jungerman and Ringel 1978, Dekker 1983). The six-vertex octahedral graph is the case .