CycleBasis returns a list of cycles in the graph, with each cycle represented as a list of vertices.  These cycles form a basis for the cycle space of G, so that every other cycle in G can be obtained from the cycle basis using only symmetric differences. (The symmetric difference is applied to cycles as sets of edges.)

The elements of the basis are also known as fundamental cycles.

The number of elements in the cycle basis (i.e., the dimension of the cycle space) is called the cyclomatic number of G.

The algorithm starts from a spanning tree of G and computes fundamental cycles for each graph obtained by adding one of the remaining edges of G to the spanning tree.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$G≔\mathrm{WheelGraph}\left(5\right)\:$

$\mathrm{Cycles}≔\mathrm{CycleBasis}\left(G\right)$

$\mathrm{Cycles}≔\left[\left[0\,1\,2\right]\,\left[0\,1\,5\right]\,\left[0\,2\,3\right]\,\left[0\,3\,4\right]\,\left[0\,4\,5\right]\right]$

$\mathrm{AsTrails}≔\mathrm{map}\left(\mathrm{cyc}\mapsto \left[\mathrm{op}\left(\mathrm{cyc}\right)\,\mathrm{cyc}\left[1\right]\right]\,\mathrm{Cycles}\right)\:$

$M≔\mathrm{Matrix}\left(2\,3\,\mathrm{map2}\left(\mathrm{DrawGraph}@\mathrm{HighlightTrail}\,G\,\mathrm{AsTrails}\,\mathrm{red}\,\mathrm{inplace}=\mathrm{false}\right)\right)\:$

$M\left[2,3\right]≔\mathrm{plot}\left(\mathrm{axes}=\mathrm{none}\right)\:$

$\mathrm{plots}:-\mathrm{display}\left(M\right)$

$G≔\mathrm{OctahedronGraph}\left(\right)\:$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{Cycles}≔\mathrm{CycleBasis}\left(G\right)$

$\mathrm{Cycles}≔\left[\left[1\,3\,2\,4\right]\,\left[1\,3\,2\,5\right]\,\left[1\,3\,2\,6\right]\,\left[1\,3\,5\right]\,\left[1\,3\,6\right]\,\left[1\,4\,5\right]\,\left[1\,4\,6\right]\right]$

$\mathrm{numelems}\left(\mathrm{Cycles}\right)$

$7$