Tetrahedral Graph

"The" tetrahedral graph is the Platonic graph that is the unique polyhedral graph on four nodes which is also the complete graph  and therefore also the wheel graph . It is implemented in the Wolfram Language as GraphData["TetrahedralGraph"].

The tetrahedral graph has a single minimal integral embedding, illustrated above (Harborth and Möller 1994), with maximum edge length 4.

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

The tetrahedral graph has 4 nodes, 6 edges, vertex connectivity 4, edge connectivity 3, graph diameter 1, graph radius 1, and girth 3. It has chromatic polynomial

			(1)
			(2)

and chromatic number 4. It is planar and cubic symmetric.

The tetrahedral graph is an integral graph with graph spectrum . Its automorphism group has order .

The tetrahedral graph is the line graph of the star graph , and the line graph of the tetrahedral graph is the octahedral graph.

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

The bipartite double graph of the tetrahedral graph is the cubical graph.

The following table summarizes some properties of the tetrahedral graph.

property	value
automorphism group order	24
characteristic polynomial
chromatic number	4
chromatic polynomial
circulant graph
claw-free	yes
clique number	4
graph complement name	4-empty graph
determined by spectrum	yes
diameter	1
distance-regular graph	yes
dual graph name	tetrahedral graph
edge chromatic number	3
edge connectivity	3
edge count	6
Eulerian	no
girth	3
Hamiltonian	yes
Hamiltonian cycle count	6
Hamiltonian path count	24
integral graph	yes
independence number	1
intersection array
LCF notation
line graph	yes
line graph name	octahedral graph
perfect matching graph	no
planar	yes
polyhedral graph	yes
polyhedron embedding names	tetrahedron
radius	1
regular	yes
spectrum
square-free	no
strongly regular parameters
traceable	yes
triangle-free	no
vertex connectivity	3
vertex count	4

More generally, a Johnson graph of the from  (with ) is known as an -tetrahedral graph. The 6-tetrahedral graph is a distance-regular graph with intersection array , and therefore also a Taylor graph.

REFERENCES

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 234, 1976.

Gardner, M. "Golomb's Graceful Graphs." Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983

.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.

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 266, 1998.

Royle, G. "F004A." http://www.csse.uwa.edu.au/~gordon/foster/F004A.html.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.