Spanning-subtree probability conjecture for the complete graph

Let GG be a graph with nn vertices, let sk(G)s_k(G) be the number of subtrees of GG with kk vertices, and define the spanning-subtree probability

p(G)=sn(G)k=1nsk(G).p(G)=\frac{s_n(G)}{\sum_{k=1}^n s_k(G)}.

Spanning-subtree probability conjecture. For every graph GG with nn vertices,

p(G)p(Kn).p(G)\le p(K_n).

The source states that this less restrictive conjecture is an open problem and that it would support the extremality of the complete graph.

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.