Packing edge-disjoint cycles in graphs and the cyclomatic number

摘要

For a graph G let mu(G) denote the cyclomatic number and let nu(G) denote the maximum number of edge-disjoint cycles of G. We prove that for every k >= 0 there is a finite set P(k) such that every 2-connected graph G for which mu(G) - nu(G) = k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k <= 2 exactly.