PreprintarXiv licencearXiv
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≥3, Kk∨(K1∪ Kn−k−1) uniquely minimizes this average under additional conditions.
Related
- A proof of the maximum Laplacian energy conjecture for connected graphs via a sharp eigenvalue-sum bound
- Contractable 2-connected subgraphs in minimally 3-connected graphs
- A Sublinear Minimum-Degree Condition for $2$-Connected Subgraphs of All Orders
- Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
- Average eccentricity in k-connected tournaments
BibTeX
@misc{chen2026proof,
title = {{A proof of Vince's conjecture on the average order of connected induced subgraphs}},
author = {Jungang Chen and Hongxia Ma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27553},
eprint = {2610.27553},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27553},
}
RIS
TY - UNPB
TI - A proof of Vince's conjecture on the average order of connected induced subgraphs
AU - Jungang Chen
AU - Hongxia Ma
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27553
UR - https://arxiv.org/abs/2610.27553
AB - 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≥3, K_k∨(K_1∪ K_n−k−1) uniquely minimizes this average under additional conditions.
ER -