The Vince conjecture on connected induced subgraphs asserts that a connected simple graph 
of graph order 
and minimum vertex degree
at least three has mean connected
induced subgraph order at least 
. Chen and Ma (2026) proved the conjecture, and in fact established
the strict inequality.
More precisely, if 
counts the nonempty connected inducing vertex sets
and 
is the sum of their sizes, then
 |
Equality holds iff 
is a complete graph. The
average is taken over the actual inducing sets, not over
graph isomorphism classes. Chen and Ma (2026)
credit GPT Astra, accessed through Danus, with assistance in developing some proofs.
