If
is a spanning tree of a connected, finite, undiected
graph ,
then the fundamental cycle-set of corresponding to is the set of cycles of , each consisting of one edge of together with the unique path in (Paton 1969).
There are exactly
fundamental cycles in a graph, namely one for each edge that does not belong to the spanning tree. Here, is the circuit rank, is the edge
count,
the vertex count, and the number of connected components. A set of fundamental cycles are illustrated above for the
cuboctahedral graph, together with the graph
itself and the spanning tree used to construct the
basis.
Any cycle of a graph can be expressed as a sum modulo 2 over a fundamental
cycle set of the graph (Gould 1959, Paton 1969).
Gotlieb, C. C. and nd Corneil, D. G. "Algorithms for Finding a Fundamental Set of Cycles for an Undirected Linear Graph." Comm.
ACM10, 780-783, 1967.Gross, J. T. and Yellen, J. Graph
Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 192-193,
2006.Gould, R. "The Application of Graph Theory to the Synthesis
of Contact Networks." Proc. International Symp. on the Theory of Switching,
Pt. I, Apr. 2-5, 1957. In The Annals of the Computation Laboratory of
Harvard University, Annals No. 29. Cambridge, MA: Harvard University Press,
pp. 244-292, 1959.Harary, F. Graph
Theory. Reading, MA: Addison-Wesley, pp. 37-38, 1994.Paton,
K. "An Algorithm for Finding Fundamental Cycles of a Graph." Comm. ACM12,
514-518, 1969.Sch, P. "Enumerating All Cycles in an Undirected
Graph." 9 Sep 2018. https://www.codeproject.com/Articles/1158232/Enumerating-All-Cycles-in-an-Undirected-Graph.Welch,
J. T. Jr. "A Mechanical Analysis of the Cyclic Structure of Undirected
Linear Graphs." J. ACM18, 2, 205-210, 1966.West,
D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 374,
2000.
is a spanning tree of a connected, finite, undiected
graph 
,
then the fundamental cycle-set of 
corresponding to 
is the set of cycles 
of 
, each consisting of one edge 
of 
together with the unique path 
in 
(Paton 1969).
is the circuit rank, 
is the edge
count, 
the vertex count, and 
the number of connected components. A set of 
fundamental cycles are illustrated above for the
cuboctahedral graph, together with the graph
itself and the spanning tree used to construct the
basis.
.
