A proof of Vince's conjecture on the average order of connected induced subgraphs
In the authors' words
We prove that the average order of connected induced subgraphs of a connected simple graph of order and minimum degree at least is strictly greater than , which settles a conjecture of Vince~[\emph{J. Graph Theory} 97 (2021), 82--103]. We go further and show that, for connected simple graphs of order and minimum degree exactly , uniquely minimizes this average under additional conditions.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.