Cubic graphs, also called trivalent graphs, are graphs all of whose nodes have degree 3 (i.e., 3-regular graphs). Cubic graphs on nodes exists 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 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 cubics 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. In addition, the following tables gives some named graph that are skeletons
of polyhedra.
nodes exists 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. In addition, the following tables gives some named graph that are skeletons
of polyhedra.
