The graph basis number is the smallest possible maximum number of basis cycles
containing a single edge, where the minimum is taken over all cycle
bases of
. Equivalently, a
-basis is a cycle basis in which
every edge occurs in at most
cycles, and
is the least such
(Schmeichel 1981).
A forest has basis number 0 and a cycle graph has basis number 1. Mac Lane's planarity criterion states that a graph is planar iff it has a 2-basis (Mac Lane 1937). The definition allows all cycle bases, not just those determined by spanning forests.
Knauer (2026) proved logarithmic upper bounds in each of the vertex count, circuit rank, and Euler genus. In particular, for graphs
with vertices,
as
. The proof
was developed with AI assistance and checked by the author. Independent external
review had not been reported as of Sep. 7, 2026.