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 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.
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].
,
where 
is the edge
count and 
is the vertex count.
(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 
.
, 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.
