Cubic Graph

Cubic graphs, also called trivalent graphs, are graphs all of whose nodes have degree 3 (i.e., 3-regular graphs). Here the graphs are assumed to be finite and simple. Cubic graphs on nodes exist only for even (Harary 1994, p. 15). Not-necessarily-connected cubic graphs on , 6, and 8 are illustrated above. An enumeration of cubic graphs on nodes for small is implemented in the Wolfram Language as GraphData["Cubic", n].

A necessary (but not sufficient) criterion for a graph to be cubic is that , where is the edge count and is the vertex count.

The numbers of nonisomorphic not-necessarily-connected cubic graphs on 2, 4, 6, ... nodes are 0, 1, 2, 6, 21, 94, 540, 4207, ... (OEIS A005638; Robinson and Wormald 1983). The unique 4-node cubic graph is the complete graph (the tetrahedral graph). The two 6-node cubic graphs are the circulant graphs (the utility graph) and . Three of the six 8-node cubic graphs are the cubical graph and circulant graphs and .

The connected cubic graphs have been determined by Brinkmann (1996) up to 24 nodes, and the numbers of such graphs for , 4, ... are 0, 1, 2, 5, 19, 85, 509, 4060, 41301, ... (OEIS A002851). Meringer and Royle independently maintain enumerations of connected cubic graphs.

-cage graphs are cubic. The following table gives some named cubic graphs.

graph	nodes
tetrahedral graph	4
cubical graph	8
truncated tetrahedral graph	12
dodecahedral graph	20
truncated cubical graph	24
truncated octahedral graph	24
great rhombicuboctahedral graph	48
truncated dodecahedral graph	60
truncated icosahedral graph	60
Horton 96-graph	96
great rhombicosidodecahedral graph	120
Tutte 12-cage	126

Every finite simple graph that is cubic, whether connected or not, has total edge irregularity strength , where is its vertex count (Barra et al. 2026).