The Minimum Number of Cycles in Graphs with Given Cycle Rank and Small Connectivity

The cycle rank, \(r(G)\), of a graph \(G = (V, E)\) is given by \(r(G) = |E| – |V| + 1\). Let \(f(k, r)\) be the minimum number of cycles possible in a \(k\)-connected graph with cycle rank \(r\). We show \(f(1, r) = r\), \(f(2, r) = \binom{r+1}{2}\), \(f(3, r) = r^2 – r + 1\) and characterize the extremal graphs. Bounds are obtained for \(f(k, r)\), \(k \geq 4\); the upper bound is polynomial in \(r\).