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.
See also
Barnette's Conjecture, Bicubic Graph, Cage Graph, Cubic Nonplanar Graph, Cubic Symmetric Graph, Cubical Graph, Frucht Graph, Horton Graphs, Quartic Graph, Quasi-Cubic Graph, Quintic Graph, Regular Graph, Tait's Hamiltonian Graph Conjecture, Tutte Conjecture, xyz Embedding
Explore with Wolfram|Alpha
References
Brinkmann, G. "Fast Generation of Cubic Graphs." J. Graph Th. 23, 139-149, 1996.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Meringer, M. "Connected Regular Graphs." http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Robinson, R. W.; Wormald, N. C. "Number of Cubic Graphs." J. Graph. Th. 7, 463-467, 1983.Royle, G. "All Cubic Graphs." http://people.csse.uwa.edu.au/gordon/remote/cubics/.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 177, 1990.Sloane, N. J. A. Sequences A002851/M1521 and A005638/M1656 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc. 43, 459-474, 1947.Tutte, W. T. "A Theory of 3-Connected Graphs." Indag. Math. 23, 441-455, 1961.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Cubic Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CubicGraph.html