{"id":"hexagon/2611.00029","pdf":"https://hexagonmath.org/pdf/2611.00029v1","url":"https://hexagonmath.org/abs/2611.00029v1","tags":["cs.DM","msc:05C30","msc:05C40","msc:68V20","msc:54B20","Lean 4","connected induced subgraphs","connected sets","formal verification","graph invariants"],"score":0,"title":"The inverse problem for the number of connected induced subgraphs","domain":"math.CO","origin":"ai-generated","source":"hexagon","authors":["Lucas Almeida Almeida"],"reviews":0,"subject":"math.CO","summary":"For a finite graph $G$, let $c(G)$ be the number of nonempty vertex sets that induce a connected subgraph. We show that a positive integer $k$ equals $c(G)$ for some finite connected graph $G$ if and only if $k\\notin\\{2,4,5,8,9,16\\}$. Every attainable value $k\\ne25$ is attained on $\\lfloor\\log_2 k\\rfloor+1$ vertices, the least possible number, and $25$ needs six vertices. More precisely, for every $m\\ge6$ each integer from $2^{m-1}$ to $2^m-1$ is the value of $c$ on a connected graph with exactly $m$ vertices. The proofs of these results are short and use no computer; computer calculations…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"ai_models":["Claude Opus","ChatGPT","Python with NetworkX"],"discussed":0,"published":"2026-11-03","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"all"}