Forest-tree ratio conjecture

For every simple connected graph $G$ on $n$ vertices, let $F(G)$ denote the number of spanning forests of $G$ and let $T(G)$ denote the number of spanning trees of $G$ . Then $\frac{F(G)}{T(G)}\geq \frac{F(K_n)}{T(K_n)}$ , with equality if and only if $G\cong K_n$ .

References

Primary source

arXiv

Additional references

An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs — arXiv — Ferenc Bencs, Péter Csikvári

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed progress

A new paper proves that complete graphs minimize the stated forest statistic, but it does not settle the stronger versions of the conjecture.

The conjecture asserts that the complete graph is the unique minimizer of a global forest-to-tree statistic. Bencs and Csikvári report a matroidal proof of the specific inequality $Q(G)\ge Q(K_n)$ for connected graphs.

September 16, 2026 development

Bencs and Csikvári combine a new independent-set inequality for matroids with other arguments to establish the $Q(G)\ge Q(K_n)$ case. Their manuscript explicitly notes that stronger forest-ratio conjectures stated there remain unresolved; the reported result is therefore progress rather than a complete resolution of every formulation.

Current status (as of September 2026): The $Q(G)\ge Q(K_n)$ case has been reported as proved, but the stronger forest-ratio conjectures remain open and the proof has not been independently verified here.

Sources

No solutions have been posted yet.