TOPICS

# Fundamental Cycle

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).

The Wolfram Language function FindFundamentalCycles[g] can be used to find a set of fundamental cycles of a graph .

Circuit Rank, Graph Cycle

## Explore with Wolfram|Alpha

More things to try:

## References

Gotlieb, C. C. and nd Corneil, D. G. "Algorithms for Finding a Fundamental Set of Cycles for an Undirected Linear Graph." Comm. ACM 10, 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. ACM 12, 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. ACM 18, 2, 205-210, 1966.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 374, 2000.

## Cite this as:

Weisstein, Eric W. "Fundamental Cycle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FundamentalCycle.html