Connected-graph contraction conjecture for mean subtree order

Let GG be a connected graph and let eE(G)e\in E(G). Write G/eG/e for the graph obtained by contracting ee, and let μ\mu denote mean subtree order.

Connected-graph contraction conjecture. Contracting any edge should reduce the mean subtree order by at least 13\frac13, with equality only for a path:

μ(G)μ(G/e)13,\mu(G)-\mu(G/e)\ge\frac13,

with equality if and only if GG is a path. The source presents this as a proposed generalisation of the proved tree case and says that proving it would imply the path-minimum result.

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.