← All problems

Vince’s conjecture on the average order of connected induced subgraphs

For every connected simple graph GG of order nn with minimum degree $$\delta(G)≥3(G)\ge 3, let C(G)\mathcal{C}(G) be the family of vertex sets S⊆V(G)S\subseteq V(G) such that the induced subgraph G[S]G[S] is connected. Define the average order of connected induced subgraphs by A(G)=1∣C(G)∣∑S∈C(G)∣S∣A(G)=\frac{1}{|\mathcal{C}(G)|}\sum_{S\in\mathcal{C}(G)}|S|. Then A(G)>n2A(G)>\frac{n}{2}.

References

Progress summary

Refreshed
Open · solution reported

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 33 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 A(G)≥(n+2)/3A(G) \geq (n+2)/3 for every connected graph, with equality only for paths; this concerns the global minimum, not Vince’s conjecture.
  • For kk-connected graphs, a known bound is A(G)≥n2(1−12k+1)A(G) \geq \frac{n}{2}\left(1-\frac{1}{2^k+1}\right) (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.

Sources

Solutions 0

No solutions have been posted yet.