TOPICS
Search

Mean Connected Induced Subgraph Order

The mean connected induced subgraph order of a finite graph G is the average number of vertices in its nonempty connected induced subgraphs. The average is over inducing vertex sets, not over graph isomorphism classes. Writing C(G) for those sets, it is

A(G)=(sum_(U in C(G))|U|)/(|C(G)|).

The Vince conjecture asserts A(G)>=n/2 for every connected n-vertex simple graph of minimum vertex degree at least three. Chen and Ma (2026) proved the strict inequality A(G)>n/2. Chen and Ma (2026) credit GPT Astra, accessed through Danus, with assistance in developing some proofs.

See also

Induced Subgraph, Vince Conjecture

Explore with Wolfram|Alpha

References

Chen, J. and Ma, H. "A Proof of Vince's Conjecture on the Average Order of Connected Induced Subgraphs." 20 Oct 2026. https://arxiv.org/abs/2610.27553.

Cite this as:

Weisstein, Eric W. "Mean Connected Induced Subgraph Order." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MeanConnectedInducedSubgraphOrder.html

Subject classifications