Vince’s conjecture on the average order of connected induced subgraphs
For every connected simple graph of order with minimum degree $$\delta, let be the family of vertex sets such that the induced subgraph is connected. Define the average order of connected induced subgraphs by . Then .
References
- A proof of Vince's conjecture on the average order of connected induced subgraphs — arXiv — Jungang Chen, Hongxia Ma
Source: arXiv
Progress summary
An October 2026 preprint claims to prove Vince’s conjecture and an accompanying extremal statement, but the proof has not been independently verified.
Vince’s conjecture says that graphs with minimum degree at least have average connected-induced-subgraph order at least half their order. The new claim also gives an extremal characterization under an exact-minimum-degree hypothesis.
Known results
- Haslegrave (2022) proved that for every connected graph, with equality only for paths; this concerns the global minimum, not Vince’s conjecture.
- For -connected graphs, a known bound is (2021).
October 2026 claimed proof
Jungang Chen and Hongxia Ma’s preprint claims the strict inequality in Vince’s conjecture together with the stated structural refinement. This is an unrefereed claim; the retrieved sources contain no independent mathematical assessment.
Current status (as of October 2026): The conjecture is claimed proved by Chen and Ma, but the proof and extremal characterization remain unverified.
Solutions 0
No solutions have been posted yet.