HEXAGONbeta

The inverse problem for the number of connected induced subgraphs

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricscs.DM — Discrete Mathematics

Contributed by Lucas Almeida Almeida ↗

Version 1 / Nov 03, 2026 / CC BY 4.0

Abstract

For a finite graph GG, let c(G)c(G) be the number of nonempty vertex sets that induce a connected subgraph. We show that a positive integer kk equals c(G)c(G) for some finite connected graph GG if and only if k∉{2,4,5,8,9,16}k\notin\{2,4,5,8,9,16\}. Every attainable value k≠25k\ne25 is attained on ⌊log⁡2k⌋+1\lfloor\log_2 k\rfloor+1 vertices, the least possible number, and 2525 needs six vertices. More precisely, for every m≥6m\ge6 each integer from 2m−12^{m-1} to 2m−12^m-1 is the value of cc on a connected graph with exactly mm vertices. The proofs of these results are short and use no computer; computer calculations serve only as independent checks, and for two auxiliary results: the values on six to eight vertices, and the result on all connected subgraphs described below. The value 1616 falls into a gap above the path: a connected graph on n≥4n\ge4 vertices other than the path PnP_n has at least n−3n-3 more connected sets than PnP_n. The values k≥17k\ge17 are realized by a recursive construction from cones, disjoint unions and a family of graphs that we call near-cones, starting from seven small graphs; it produces a graph with c(G)=kc(G)=k in time polynomial in log⁡k\log k. The question arose from a problem of Ordoñez in continuum theory, through a reduction by Camargo, Ordoñez and Ramírez, who found the values up to 255255 by a computer search. The proof is formalized in Lean 4. We also observe that a theorem of Czabarka, Székely and Wagner on subtrees reduces the corresponding problem for the number of all connected subgraphs to a finite computation, and we report its outcome. We did not find these results in the literature, but we make no claim of novelty or priority.

Provenance statement

Artificial intelligence was used extensively in this work, both to obtain the results and to check them. Solving and proving. The main model used to solve the problem and prove the theorems was Claude Opus 5.5 (Anthropic). In an iterative process directed by the author, it carried out most of the exploratory proof development (including the near-cones of Section 4 and the arguments of Section 3), wrote and ran the programs of Section 9, carried out the literature search of Section 1.2, and generated most of the first draft of the manuscript and of the Lean 4 formalization of Section 8. Reading and checking. ChatGPT-Astra (OpenAI) was used, together with the author, to read the manuscript and check the arguments, with repeated rounds of proofreading, proof checking and comparison of proofs (for example the two proofs of Proposition 3.2 and the two exclusions of 16 on five vertices). In each round the author and ChatGPT-Astra reviewed the text, the proofs and the supplementary material and sent feedback, and Claude revised them. The author's role. The author formulated the problem (it arose from Questions 3.5 and 3.21 of Camargo, Ordoñez and Ramírez), provided the mathematical context and constraints, steered the iterations through prompts and feedback, supplied ideas and strategies, selected and revised the outputs, and reviewed the final arguments. Verification. Programs check the explicit finite counts (Section 9), and the results listed in Table 7 are formally verified in Lean 4 with Mathlib (Section 8): no sorry, no native_decide, no added axioms; replayed with leanchecker and checked with nanoda. No independent expert has yet verified the proofs. The author takes full responsibility for the content. Code, data and the Lean formalization: https://github.com/LucasAlves8Sp/THE-INVERSE-PROBLEM-FOR-THE-NUMBER-OF-CONNECTED-INDUCED-SUBGRAPHS

Tools used

Anthropic
Claude OpusVersion 5.5
OpenAI
ChatGPTVersion Astra
Lean
LeanVersion 4.35.0 with Mathlib
Python Software Foundation
Python with NetworkXVersion 3.13 (NetworkX 3.7)

References

  1. Y. Alizadeh, N. Bašić, I. Damnjanović, T. Došlić, T. Pisanski, D. Stevanović, and K. Xu, Solving the Mostar index inverse problem , preprint, 2312.13083 .
  2. L. Alves de Almeida, All finite cardinalities of the hyperspace of regular subcontinua , preprint, version 2.3, 2026, available in Rep .
  3. L. Alves de Almeida, The inverse problem for the number of connected induced subgraphs: paper, Lean formalization and programs , GitHub repository, .
  4. L. Alves de Almeida, All finite cardinalities of the hyperspace of regular subcontinua: paper, programs and Lean formalization , GitHub repository, .
  5. E. O. D. Andriantiana and A. A. V. Dossou-Olory, Nordhaus--Gaddum inequalities for the number of connected induced subgraphs in graphs , preprint, 2006.01187 .
  6. C. Bernert and J. Shaw, The inverse problem for the Steiner--Wiener index via additive number theory , preprint, 2026, 2603.17559 .
  7. J. Camargo, N. Ordoñez, and D. Ramírez, On the hyperspaces of meager and regular continua , Appl. Gen. Topol. 25 (2024), no. 2, 385--406. 10.4995/agt.2024.20116.DOI
  8. É. Czabarka, L. A. Székely, and S. Wagner, The inverse problem for certain tree parameters , Discrete Appl. Math. 157 (2009), no. 15, 3314--3319. 10.1016/j.dam.2009.07.004.DOI
  9. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, Cham, 2021, 625--635. 10.1007/978-3-030-79876-5_37.DOI
  10. A. A. V. Dossou-Olory, Graphs and unicyclic graphs with extremal number of connected induced subgraphs , preprint, 1812.02422 .
Show all 25 referencesShow fewer references
  1. A. A. V. Dossou-Olory, Cut and pendant vertices and the number of connected induced subgraphs of a graph , preprint, 1910.04552 .
  2. A. A. V. Dossou-Olory, On the maximum number of connected induced subgraphs of a graph , preprint, 2023, 2303.01964 .
  3. A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring network structure, dynamics, and function using NetworkX , in: Proceedings of the 7th Python in Science Conference (SciPy 2008), 11--15.
  4. J. Haslegrave, The number and average size of connected sets in graphs with degree constraints , preprint, 2105.13332 .
  5. V. Linek, Bipartite graphs can have any number of independent sets , Discrete Math. 76 (1989), 131--136. 10.1016/0012-365X(89)90306-3.DOI
  6. The mathlib Community, The Lean mathematical library , in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), 367--381. 10.1145/3372885.3373824.DOI
  7. OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , sequences A001187 and A001349, https://oeis.org.link
  8. N. Ordoñez, The hyperspace of regular subcontinua , Topology Appl. 234 (2018), 415--427. 10.1016/j.topol.2017.11.038.DOI
  9. D. Pandey and K. L. Patra, On the number of connected subgraphs of graphs , Indian J. Pure Appl. Math. 52 (2021), no. 2, 571--583. 10.1007/s13226-021-00061-4.DOI
  10. R. C. Read and R. J. Wilson, An Atlas of Graphs , Oxford University Press, Oxford, 1998.
  11. L. A. Székely and H. Wang, On subtrees of trees , Adv. in Appl. Math. 34 (2005), 138--155. 10.1016/j.aam.2004.07.002.DOI
  12. P. Tittmann, I. Averbouch, and J. A. Makowsky, The enumeration of vertex induced subgraphs with respect to the number of components , European J. Combin. 32 (2011), no. 7, 954--974. 10.1016/j.ejc.2011.03.017.DOI
  13. A. Vince, Counting connected sets and connected partitions of a graph , Australas. J. Combin. 67 (2017), no. 2, 281--293.
  14. H. Wang and G. Yu, All but 49 numbers are Wiener indices of trees , Acta Appl. Math. 92 (2006), 15--20. 10.1007/s10440-006-9037-2.DOI
  15. S. Wernicke, Efficient detection of network motifs , IEEE/ACM Trans. Comput. Biol. Bioinform. 3 (2006), no. 4, 347--359. 10.1109/TCBB.2006.51.DOI

Version history

  1. v1Submitted by Lucas Almeida AlmeidaInitial depositCurrentNov 02, 2026