Almost-spanning subtree ratio conjecture for the complete graph

About 1 year old · traced to

Let GG be a graph of order nn. For 1≤k≤n1\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,

sn−1(G)≥sn−1(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.

References

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.