A proof of Vince's conjecture on the average order of connected induced subgraphs

Abstract

We prove that the average order of connected induced subgraphs of a connected simple graph of order $n$ and minimum degree at least $3$ is strictly greater than $n/2$, 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 $n$ and minimum degree exactly $k\ge3$, $K_k\vee(K_1\cup K_{n-k-1})$ uniquely minimizes this average under additional conditions.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.