HEXAGONbeta

Contracting a pendant edge can increase the mean subtree order

Primarily AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Alexander Kramer

Version 2 / Nov 06, 2026 / CC0 1.0

Abstract

Cambie, Jooken and Wagner conjectured that contracting an edge of a connected graph decreases the mean subtree order by at least 1/3, as it does for trees. We construct unicyclic graphs of order n and maximum degree 3 in which contracting a pendant edge increases the mean subtree order by n/450+O(1), disproving the conjecture. In this family the bound first fails at 481 vertices and contraction first increases the mean at 631 vertices.

Provenance statement

This note was developed with multiple large language models from OpenAI and Anthropic under my direction. I directed the construction and the writing, edited the text directly, worked through the proof sentence by sentence, and checked and revised the argument and text.

Tools used

Anthropic
Claude Fable
OpenAI
Codex

References

  1. S. Cambie, J. Jooken and S. Wagner, On the extrema of the mean subtree order of graphs, arXiv:2508.20593 (2025), version 2 (2026).arXiv
  2. R. E. Jamison, On the average number of nodes in a subtree of a tree, J. Combin. Theory Ser. B 35 (1983), 207--223.
  3. R. E. Jamison, Monotonicity of the mean order of subtrees, J. Combin. Theory Ser. B 37 (1984), 70--78.
  4. Z. Luo, K. Xu, S. Wagner and H. Wang, On the mean subtree order of trees under edge contraction, J. Graph Theory 102 (2023), 535--551.
  5. R. Wang, On the difference of mean subtree orders under edge contraction, J. Combin. Theory Ser. B 169 (2024), 45--62.

Version history

  1. v1 · 2 pagesSubmitted by Alexander KramerInitial depositSupersededNov 06, 2026
  2. v2 · 2 pagesSubmitted by Alexander KramerSubmitted as a new versionCurrentNov 06, 2026