There exists a universal constant C>0 such that every finite simple graph G with n=|V(G)|≥ 2 satisfies bn(G)≤ Clog n, where bn(G) is the minimum, over all bases B of the cycle space of G over F_2, of the edge-congestion max_e∈ E(G)|C∈B:e∈ E(C)|.

Logarithmic basis number conjecture for graphs

The conjecture asserts that every graph on $n$ vertices has basis number $\mathrm{bn}(G)=O(\log n)$ . The reported result resolves a conjecture of Miraftab, Morin and Yuditsky and an earlier question of Bazargani, Biedl, Bose, Maheshwari and Miraftab.

Known results

Lehner and Miraftab (2024): graphs on surfaces of genus $g$ satisfy $\mathrm{bn}(G)=O(\log^2 g)$ ; non-planar toroidal graphs have basis number $3$ .
Geniet and Giocanti: $H$ -minor-free graphs have bounded basis number, with a previously very large treewidth bound.
Miraftab, Morin and Yuditsky (2025): their independent results contribute to polynomial bounds for $H$ -minor-free graphs.

September 2, 2026 claimed resolution

A preprint titled Logarithmic basis number of graphs claims $\mathrm{bn}(G)=O(\log n)$ , with refinements $O(\log \beta(G))$ in cycle rank and $O(\log g)$ in Euler genus, and says these orders are best possible. It therefore claims a complete resolution, but the source is explicitly unrefereed.

Current status (as of September 2026): The conjecture is claimed proved by an unrefereed preprint, but independent verification is not recorded.

Logarithmic basis number conjecture for graphs

Primary source

Additional references

Progress summary

Solutions 0