{"id":"arxiv/2610.27553","url":"https://arxiv.org/abs/2610.27553","tags":["math.CO"],"score":0,"title":"A proof of Vince's conjecture on the average order of connected induced subgraphs","domain":"math.CO","source":"arxiv","authors":["Jungang Chen","Hongxia Ma"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-20","reactions":{}}