Almost-spanning subtree ratio conjecture for the complete graph

Let GG be a graph of order nn. For 1kn1\le k\le n, let sk(G)s_k(G) denote the number of subtrees of GG with kk vertices; in particular, sn(G)s_n(G) counts spanning trees.

Almost-spanning subtree ratio conjecture. For every graph GG of order nn,

sn1(G)sn1(Kn)sn(Kn)sn(G).s_{n-1}(G)\ge \frac{s_{n-1}(K_n)}{s_n(K_n)}s_n(G).

This is proposed as a reduction toward proving that the complete graph has greatest mean subtree order. Its status is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Jorik Jooken and Stephan Wagner, “On the extrema of the mean subtree order of graphs”, arXiv:2508.20593 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.