\documentclass[11pt]{amsart} \usepackage{upquote} \usepackage{amssymb} \usepackage[margin=1in]{geometry} \usepackage{enumitem} \usepackage{tikz} \usepackage{booktabs} \usepackage{multicol} \usepackage{longtable} \usepackage{array} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{question}[theorem]{Question} \newtheorem{introtheorem}{Theorem} \renewcommand{\theintrotheorem}{\Alph{introtheorem}} \newtheorem{introcorollary}[introtheorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{construction}[theorem]{Construction} \newtheorem{example}[theorem]{Example} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\cl}{\operatorname{cl}} \newcommand{\intr}{\operatorname{int}} \newcommand{\D}{\mathcal{D}} \newcommand{\N}{\mathbb{N}} \newcommand{\Lam}{\Lambda} \newcommand{\Tr}[1]{T(#1)} \newcommand{\bd}{\operatorname{bd}} \newcommand{\doi}[1]{\href{https://doi.org/#1}{doi:\nolinkurl{#1}}} % a finite stage of the Knaster bucket-handle continuum in the unit frame: % upper semicircles about (1/2,0) through the fourth-stage Cantor endpoints, % lower semicircles about 5/(2*3^n), n = 1,...,4 (as in the previous paper) \newcommand{\knaster}{% \foreach \r in {0.5,0.48765,0.47531,0.46296,0.42593,0.41358,0.40123,0.38889,0.27778,0.26543,0.25309,0.24074,0.2037,0.19136,0.17901,0.16667} {\draw ({0.5+\r},0) arc[start angle=0,end angle=180,radius=\r];} \foreach \r in {0.16667,0.15432,0.14198,0.12963,0.09259,0.08025,0.0679,0.05556} {\draw ({0.83333-\r},0) arc[start angle=180,end angle=360,radius=\r];} \foreach \r in {0.05556,0.04321,0.03086,0.01852} {\draw ({0.27778-\r},0) arc[start angle=180,end angle=360,radius=\r];} \foreach \r in {0.01852,0.00617} {\draw ({0.09259-\r},0) arc[start angle=180,end angle=360,radius=\r];} \draw ({0.03086-0.00617},0) arc[start angle=180,end angle=360,radius=0.00617];} \begin{document} \title[Finite cardinalities of $\D(X)$]{All finite cardinalities of the hyperspace of regular subcontinua} \author{Lucas Alves de Almeida} \address{Independent researcher} \email{lucasderiva8x@gmail.com} \subjclass[2020]{Primary 54B20; Secondary 54F15, 05C30} \keywords{Continuum, hyperspace, regular subcontinuum, indecomposable continuum, connected induced subgraph, inverse problem} \begin{abstract} For a metric continuum $X$, let $\D(X)$ be the family of subcontinua $A$ of $X$ with $A=\cl_X\intr_XA$. Ordo\~nez asked which finite numbers occur as $|\D(X)|$. Camargo, Ordo\~nez and Ram\'irez excluded $2,4,5,8,9$ and asked whether every $k\ge256$ occurs. We prove that a positive integer $k$ equals $|\D(X)|$ for some metric continuum $X$ if and only if $k\notin\{2,4,5,8,9,16\}$. The finite cardinalities of $\D(X)$ are exactly the numbers of vertex sets inducing connected subgraphs of finite connected graphs; every finite connected graph is realized by copies of the Knaster continuum glued at points. We determine the values of this graph invariant without computer assistance. A short argument excludes $16$, and an explicit recursive family of graphs realizes every $k\ge17$ with the least possible number of vertices. Consequently, for $k\ge32$ the least number of minimal regular subcontinua of a continuum $X$ with $|\D(X)|=k$ is $\lfloor\log_2k\rfloor+1$. Programs check the explicit finite graph counts, and Theorem~A is formally verified in Lean. \end{abstract} \maketitle \section{Introduction}\label{sec:intro} A \emph{continuum} is a nonempty compact connected metric space. For a continuum $X$, let $C(X)$ be its hyperspace of nonempty subcontinua with the Hausdorff metric. A subcontinuum $A$ of $X$ is \emph{regular} if $A=\cl_X\intr_XA$, the closure in $X$ of the interior of $A$ in $X$. The hyperspace \[ \D(X)=\{A\in C(X): A=\cl_X\intr_XA\} \] was introduced by Ordo\~nez \cite{Or18}. Since $X\in\D(X)$, always $|\D(X)|\ge1$. For example, every nondegenerate closed subinterval of $[0,1]$ is regular in $[0,1]$, so $\D([0,1])$ is infinite. At the other extreme, a continuum is \emph{indecomposable} if it is not the union of two proper subcontinua. Every proper subcontinuum of an indecomposable continuum has empty interior \cite[Chapter~XI]{Na}, so then $\D(X)=\{X\}$ \cite[Theorem~3.7]{Or18}. The hyperspace $\D(X)$ is compact if and only if it is finite \cite[Corollary~4.13]{Or18}. Further properties of $\D(X)$ and of the hyperspace of subcontinua with empty interior are studied in \cite{Or21}. Ordo\~nez posed the following problem \cite[Problem~4.14]{Or18}, repeated as \cite[Question~3.5]{CORa} and \cite[Pregunta~3.1.6]{Ra}. \begin{question}\label{q:35} For which $n\in\N$ does there exist a continuum $X$ such that $\D(X)$ has exactly $n$ elements? \end{question} Chains, cycles and bouquets of $n$ indecomposable continua give $n(n+1)/2$, $n(n-1)+1$ and $2^n-1$ regular subcontinua \cite[Proposition~4.15]{Or18}, \cite[Proposici\'on~3.1.7]{Ra}. An element of $\D(X)$ is \emph{minimal} if it contains no other element of $\D(X)$, that is, if it is minimal with respect to inclusion; we call it a \emph{minimal regular subcontinuum}. Camargo, Ordo\~nez and Ram\'irez \cite{CORa} showed that a finite $\D(X)$ is determined by its minimal elements, which have pairwise disjoint interiors and cover $X$ \cite[Theorem~3.16]{CORa}; this reduces the count to a problem about graphs. They proved $|\D(X)|\notin\{2,4,5,8,9\}$ \cite[Proposition~3.18]{CORa},\footnote{The abstract of \cite{CORa} and the outline at the end of its Section~1 also list $3$ among the excluded values. This is a misprint: $3$ occurs, for instance for two indecomposable continua meeting in one point \cite[Proposition~4.15]{Or18}, \cite[Proposition~3.17]{CORa}.} and a computer search over graphs with at most eight vertices showed that $16$ does not occur while every integer from $17$ to $255$ does \cite[Remark~3.20]{CORa}. They asked: \begin{question}[{\cite[Question~3.21]{CORa}}]\label{q:321} If $k\ge256$, does there exist a continuum $X$ such that $|\D(X)|=k$? \end{question} The thesis \cite[Pregunta~3.1.13]{Ra} asks whether $|\D(X)|=2^n$ for some $n>0$. Both questions are special cases of the problem of characterizing the spaces homeomorphic to some $\D(X)$ \cite[Problem~3.22]{CORa}. For a finite simple graph $G$, a \emph{connected set} of $G$ is a nonempty set of vertices inducing a connected subgraph, and $c(G)$ denotes the number of connected sets. Singletons are connected sets and the empty set is not; distinct vertex sets are counted separately even when they induce isomorphic subgraphs. For a tree, $c(G)$ is the number of subtrees. \begin{introtheorem}\label{thm:A} For a positive integer $k$, the following are equivalent. \begin{enumerate}[label=\textup{(\arabic*)}] \item There is a continuum $X$ with $|\D(X)|=k$. \item There is a finite connected graph $G$ with $c(G)=k$. \item $k\notin\{2,4,5,8,9,16\}$. \end{enumerate} Moreover, for every $k\ge32$ the continuum in \textup{(1)} can be chosen as the union of $\lfloor\log_2k\rfloor+1$ copies of the Knaster continuum, any two of which meet in at most one point. No continuum with $|\D(X)|=k$ has fewer minimal regular subcontinua. \end{introtheorem} \begin{introcorollary}\label{cor:B} \begin{enumerate}[label=\textup{(\alph*)}] \item The answer to Question~\ref{q:321} is yes for every $k\ge256$; in fact $|\D(X)|=k$ occurs for every $k\ge17$. \item A finite metric space $S$ is homeomorphic to $\D(X)$ for some continuum $X$ if and only if $S$ is nonempty and $|S|\notin\{2,4,5,8,9,16\}$. This settles the finite case of \cite[Problem~3.22]{CORa}. \item There is a continuum $X$ with $|\D(X)|=2^m$ if and only if $m=0$ or $m\ge5$. This answers \cite[Pregunta~3.1.13]{Ra}. \end{enumerate} \end{introcorollary} The equivalence of (1) and (2) is Theorem~\ref{thm:reduction}. The implication (1)$\Rightarrow$(2) is the reduction of \cite{CORa}. For (2)$\Rightarrow$(1) we glue copies of the Knaster continuum along the edges of $G$ (Construction~\ref{con:XG}). The key step, Lemma~\ref{lem:key}, shows that a regular subcontinuum meeting the interior of a piece contains that piece. Its proof is direct; it does not use the discreteness hypothesis of \cite[Theorem~3.16]{CORa}, and it does not depend on where the attachment points lie. The equivalence of (2) and (3) is purely combinatorial (Sections~\ref{sec:small} and~\ref{sec:large}). The value $16$ is excluded by a short argument about spanning trees. Every $k\ge17$ is realized by a recursive construction. The construction uses cones, disjoint unions, a family of \emph{near-cones}, and seven small graphs. This part needs no computer, and it realizes $k$ with the least possible number of vertices. Theorem~A is formally verified in Lean (Section~\ref{sec:computation}). For trees, the analogous problem was solved by Czabarka, Sz\'ekely and Wagner \cite{CSW}: every positive integer except $34$ explicit values, the largest being $89$, is the number of subtrees of some tree. Their theorem gives a second, computer-assisted route to the values $k\ge90$; we recomputed its computer-assisted parts (Section~\ref{sec:computation}). The invariant $c(G)$ is a specialization of the subgraph component polynomial of Tittmann, Averbouch and Makowsky \cite{TAM}, which counts the vertex sets of $G$ by their size and by the number of components of the induced subgraph: $c(G)$ is the number of vertex sets inducing exactly one component. To our knowledge, the inverse problem for $c(G)$ over general graphs has not been treated before. A companion note \cite{Ill} illustrates the construction on the examples $|\D(X)|=1,3,6,7,11,17$. \section{Connected sets in graphs}\label{sec:graphs} Graphs are finite and simple; they need not be connected, and the graph with no vertices is allowed. For a graph $G$, we write $|G|=|V(G)|$ for its order, and for $F\subseteq V(G)$, $G[F]$ is the induced subgraph. A \emph{connected set} is a nonempty $F$ with $G[F]$ connected. We write $c(G)$ for the number of connected sets, $c_v(G)$ for the number of connected sets containing a vertex $v$, and $\Tr{n}=n(n+1)/2$. If $G$ is a tree, a connected subgraph of $G$ is the induced subgraph on its vertex set, so $c(G)$ is the number of subtrees of $G$ in the sense of \cite{SW,CSW}. For integers $a\le b$ we write $[a,b]=\{a,a+1,\dots,b\}$. For sets $A,B$ of integers and an integer $t$ we write $t+A=\{t+a:a\in A\}$ and $A+B=\{a+b:a\in A,\ b\in B\}$. A vertex is \emph{universal} if it is adjacent to every other vertex. The \emph{cone} over a graph $H$ is obtained by adding one new vertex adjacent to every vertex of $H$, which is then universal. A \emph{pendant vertex} is a vertex of degree one. A \emph{spider} consists of a vertex, its \emph{centre}, and paths, its \emph{legs}, each joined to the centre by an edge at one of its ends and otherwise disjoint from each other; the \emph{length} of a leg is its number of vertices, not counting the centre. \begin{lemma}\label{lem:rules} Let $G$, $H$ and $K$ be graphs. \begin{enumerate}[label=\textup{(\alph*)}] \item If $G$ is the disjoint union of $H$ and $K$, then $c(G)=c(H)+c(K)$. \item If $H$ is a spanning subgraph of $G$, then $c(H)\le c(G)$. If some edge of $G$ is not an edge of $H$, then $c(H)0$ be smaller than half the least distance between distinct points of the finite set $\xi\cup\eta\cup P$. The $\varepsilon$-neighbourhoods of $\xi$ and of $\eta$ are disjoint. Each of them contains no point of $P$ outside $\xi$, respectively $\eta$, so they are saturated, and their images are disjoint open sets. \emph{Metrizability.} Let $\mathcal B$ be a countable base of $Y$ closed under finite unions. Every fibre of $q$ is finite, so if $z\in W$ with $W$ open in $X_G$, some $V\in\mathcal B$ satisfies $q^{-1}(z)\subseteq V\subseteq q^{-1}(W)$, and then $z\in X_G\setminus q(Y\setminus V)\subseteq W$. As $q$ is closed, these sets form a countable base of $X_G$. A compact Hausdorff space with a countable base is metrizable by Urysohn's theorem. \emph{Connectedness.} The sets $N_i$ are connected, $N_i\cap N_j\neq\emptyset$ for $ij\in E$, and $G$ is connected, so $X_G=\bigcup_iN_i$ is connected (Lemma~\ref{lem:union}(a)). (b) No two points of $Q_i$ are identified, and a continuous injection of a compact space into a Hausdorff space is an embedding. (c) A point of $N_i\cap N_j$ is a class meeting $Q_i$ and $Q_j$; the only such class is $\{p_{ij},p_{ji}\}$, which exists exactly when $ij\in E$. (d) The set $Q_i\setminus P$ is open in $Y$ and saturated, so its image $N_i\setminus B_i$ is open in $X_G$. A point $q(p_{ij})\in B_i$ is not interior to $N_i$: each of its neighbourhoods contains the images of infinitely many points of $Q_j$ near $p_{ji}$, and only one point of $Q_j$ maps into $N_i$. Density holds because $B_i$ is finite and $N_i$ has no isolated points. (e) By (d), $\cl\intr N_i=N_i$. If $i\ne j$, then $\intr N_i\cap\intr N_j\subseteq(N_i\cap N_j)\setminus B_i=\emptyset$ by (c). \end{proof} We use the boundary bumping theorem in the following form. \begin{lemma}[Boundary bumping]\label{lem:bb} Let $K$ be a continuum and let $A$ be a nonempty proper closed subset of $K$. Then every component of $A$ meets $\bd_KA$. \end{lemma} \begin{proof} This is a form of the boundary bumping theorem \cite[Chapter~V]{Na}; we include the short proof. Since $A$ is closed, $\bd_KA=A\setminus\intr_KA$. Suppose that a component $C$ of $A$ satisfies $C\subseteq\intr_KA$. In the compact space $A$, the component $C$ is the intersection of the subsets of $A$ that are open and closed in $A$ and contain $C$ \cite[Theorem~6.1.23]{En}. The compact set $A\setminus\intr_KA$ is covered by the complements of these sets, so finitely many of them have an intersection $D$ with $C\subseteq D\subseteq\intr_KA$, and $D$ is open and closed in $A$. Then $D$ is closed in $K$. Also $D=O\cap A$ for some open $O\subseteq K$, so $D=O\cap\intr_KA$ is open in $K$. As $\emptyset\ne D\subseteq A\ne K$, this contradicts the connectedness of $K$. \end{proof} The next lemma is the key step. The intersection $K\cap N_i$ of a regular subcontinuum $K$ with a piece need not be connected, so the indecomposability of $N_i$ cannot be applied to it directly. Boundary bumping shows that $K\cap N_i$ has only finitely many components, each containing an attachment point. If every component were a proper subcontinuum of $N_i$, their union would be nowhere dense in $N_i$, while the regularity of $K$ forces $K\cap N_i$ to contain a nonempty open subset of $N_i$. \begin{lemma}[Key lemma]\label{lem:key} Let $K\in\D(X_G)$ and $1\le i\le k$. If $K\cap\intr N_i\ne\emptyset$, then $N_i\subseteq K$. \end{lemma} \begin{proof} For $k=1$ this is the indecomposability of $Q$, so let $k\ge2$. Since $K$ is regular, $\intr K$ is dense in $K$; as $\intr N_i$ is an open set meeting $K$, it meets $\intr K$. So $W=\intr K\cap\intr N_i$ is nonempty. It is open in $X_G$, hence open in $N_i$. Put $A=K\cap N_i$, a closed subset of $K$ containing $W$. If $K\subseteq N_i$, then $K$ is a subcontinuum of $N_i$ with nonempty interior in $N_i$. Since $N_i$ is indecomposable, $K=N_i$. Suppose $K\not\subseteq N_i$. Then $A$ is a nonempty proper closed subset of the continuum $K$. Every point of $A$ outside $B_i$ belongs to $K\cap\intr N_i$, which is open in $K$ and contained in $A$. Consequently $\bd_KA\subseteq B_i$. By Lemma~\ref{lem:bb}, every component of $A$ meets $B_i$. Distinct components are disjoint, so $A$ has at most $|B_i|$ components, and each of them is a subcontinuum of $N_i$. If all of them were proper subcontinua of $N_i$, each would be nowhere dense in $N_i$ by indecomposability, and so would their finite union $A$. This contradicts $W\subseteq A$. Thus some component of $A$ equals $N_i$, and $N_i\subseteq K$. \end{proof} \begin{proposition}\label{prop:realization} For every finite connected graph $G$, \[ \D(X_G)=\Bigl\{\bigcup_{i\in F}N_i: F \text{ a connected set of } G\Bigr\}, \] and distinct connected sets give distinct elements. In particular $|\D(X_G)|=c(G)$. \end{proposition} \begin{proof} The case $k=1$ is $\D(Q)=\{Q\}$. Let $k\ge2$. By Lemma~\ref{lem:XG}(c), the intersection graph of $N_1,\dots,N_k$ is $G$. By Lemma~\ref{lem:union} and Lemma~\ref{lem:XG}(e), for every connected set $F$ the set $N_F$ is a regular subcontinuum, and $F\mapsto N_F$ is injective. Conversely, let $K\in\D(X_G)$ and $F=\{i:K\cap\intr N_i\ne\emptyset\}$. By Lemma~\ref{lem:key}, $N_F\subseteq K$. The set $\bigcup_i\intr N_i=X_G\setminus(B_1\cup\dots\cup B_k)$ is the complement of a finite set in a space without isolated points, so $\intr K\cap\bigcup_i\intr N_i$ is dense in $\intr K$. This set is contained in $N_F$. Therefore $K=\cl\intr K\subseteq N_F$. So $K=N_F$; moreover $F\ne\emptyset$, and $F$ is connected by Lemma~\ref{lem:union}(a). \end{proof} \begin{remark}[Position of the attachment points]\label{rem:composants} Recall that the \emph{composant} of a point $x$ in a continuum is the union of all proper subcontinua containing $x$. Lemma~\ref{lem:key} does not depend on where the attachment points lie, but the choice of attachment points does affect which proper subcontinua $X_G$ has. If two attachment points $q(p_{ij})$ and $q(p_{il})$ of $N_i$ lie in one composant of $N_i$, then a proper subcontinuum $C$ of $N_i$ contains both, and $L=N_j\cup C\cup N_l$ is a subcontinuum of $X_G$ that is not a union of pieces. It is not regular. The set $\intr L\setminus(N_j\cup N_l)$ is open in $X_G$ and contained in $C$, hence open in $N_i$, and it is empty because $C$ is nowhere dense in $N_i$. So $\cl\intr L\subseteq N_j\cup N_l$ misses the nonempty set $C\setminus(N_j\cup N_l)$. Thus attachment points in a common composant create additional subcontinua, but the regular subcontinua are still exactly the connected unions of pieces. What matters is that each $B_i$ is finite: this bounds the number of components of $K\cap N_i$ in Lemma~\ref{lem:key}. In the construction of \cite{AA}, with countably many attachment points on a piece, the composants do matter. \end{remark} \begin{theorem}\label{thm:reduction} The set of finite cardinalities of hyperspaces $\D(X)$, over all continua $X$, equals the set of values $c(G)$ over all finite connected graphs $G$. \end{theorem} \begin{proof} Combine Propositions~\ref{prop:necessity} and~\ref{prop:realization}. \end{proof} \section{The values up to sixteen}\label{sec:small} For $m\ge0$ let \begin{align*} \Lam_m&=\{c(K): K\text{ a graph with exactly }m\text{ vertices}\},\\ V_m&=\{c(G): G\text{ a connected graph with exactly }m\text{ vertices}\}, \end{align*} so that $\Lam_0=\{0\}$ and $V_m\subseteq\Lam_m$. By Lemma~\ref{lem:rules}(f), $V_m\subseteq[\Tr{m},2^m-1]$. \begin{lemma}\label{lem:upto4} $V_1=\{1\}$, $V_2=\{3\}$, $V_3=\{6,7\}$ and $V_4=\{10,11,12,13,14,15\}$. \end{lemma} \begin{proof} Up to isomorphism, the connected graphs on at most three vertices are $K_1$, $K_2$, $P_3$ and $K_3$, and the six connected graphs on four vertices are the path, the star, the paw (a triangle with one pendant vertex), the cycle, the diamond ($K_4$ minus an edge) and $K_4$. Lemma~\ref{lem:rules} and Example~\ref{ex:formulas} give $10$, $11$, $12$, $13$, $14$ and $15$. For the cycle, the connected sets are the $12$ proper cyclic intervals of vertices together with the whole vertex set. These agree with \cite[Figure~3]{CORa}. \end{proof} \begin{proposition}\label{prop:no16} No connected graph $G$ satisfies $c(G)=16$. \end{proposition} \begin{proof} Let $G$ be connected with $n$ vertices and $c(G)=16$. By Lemma~\ref{lem:rules}(f), $\Tr{n}\le16$, so $n\le5$, and $2^n-1\ge16$, so $n\ge5$. Thus $n=5$. The trees on five vertices are the path $P_5$, the spider with legs of lengths $2$, $1$ and $1$, and the star $K_{1,4}$. By Example~\ref{ex:formulas}(i) they have $c=15$, $3\cdot2\cdot2+3+1+1=17$ and $2^4+4=20$. Let $S$ be a spanning tree of $G$. If $S$ is the spider or the star, then $c(G)\ge c(S)\ge17$ by Lemma~\ref{lem:rules}(b). Suppose $S=P_5$, with vertices $v_1,\dots,v_5$ in order, and $G\ne P_5$. Then $G$ contains $P_5$ plus a chord $v_av_b$ with $b\ge a+2$. A set that is connected in $P_5+v_av_b$ but not in $P_5$ consists of two intervals of the path, one containing $v_a$ and the other containing $v_b$, separated by at least one vertex. So these sets are $\{v_\alpha,\dots,v_x\}\cup\{v_y,\dots,v_\beta\}$ with $\alpha\le a\le x$ and $x+2\le y\le b\le\beta$. The outer ends can be chosen in $a$ ways ($1\le\alpha\le a$) and in $6-b$ ways ($b\le\beta\le5$). The inner ends must satisfy $a\le x$, $x+2\le y\le b$, which leaves $\Tr{b-a-1}$ choices. Thus the chord adds $a(6-b)\Tr{b-a-1}$ connected sets. For the six possible chords $(a,b)=(1,3)$, $(2,4)$, $(3,5)$, $(1,4)$, $(2,5)$, $(1,5)$ this number is $3$, $4$, $3$, $6$, $6$, $6$, so it is always at least $3$. Hence $c(G)\ge c(P_5+v_av_b)\ge18$ by Lemma~\ref{lem:rules}(b). In every case $c(G)\ne16$. \end{proof} Table~\ref{tab:n5} lists representatives of the $21$ isomorphism classes of connected graphs on five vertices; with Lemma~\ref{lem:upto4} it covers all $31$ classes of connected graphs with at most five vertices. It confirms that $V_5=\{15\}\cup[17,24]\cup[26,31]$. \begin{table}[ht] \centering \small \begin{tabular}{rlr@{\qquad}rlr} \toprule & edges & $c$ & & edges & $c$\\ \midrule 1 & 04 13 23 24 & 15 & 12 & 03 04 12 14 23 34 & 24\\ 2 & 04 14 23 34 & 17 & 13 & 04 12 13 14 23 24 34 & 24\\ 3 & 04 12 13 23 34 & 18 & 14 & 03 04 13 14 23 24 & 26\\ 4 & 04 13 23 24 34 & 19 & 15 & 03 04 12 14 23 24 34 & 26\\ 5 & 04 14 24 34 & 20 & 16 & 03 04 13 14 23 24 34 & 27\\ 6 & 04 14 23 24 34 & 21 & 17 & 03 04 12 13 14 23 24 & 27\\ 7 & 04 13 14 23 24 & 21 & 18 & 03 04 12 13 14 23 24 34 & 28\\ 8 & 03 04 12 14 23 & 21 & 19 & 02 03 04 12 13 14 24 34 & 29\\ 9 & 04 12 13 23 24 34 & 22 & 20 & 02 03 04 12 13 14 23 24 34 & 30\\ 10 & 03 04 12 14 24 34 & 22 & 21 & all ten edges & 31\\ 11 & 04 13 14 23 24 34 & 23 & & & \\ \bottomrule \end{tabular} \caption{Representatives of the $21$ isomorphism classes of connected graphs on five vertices, with their values of $c$. Each representative is the canonical labeled graph of Appendix~\ref{app:witnesses}, on the vertex set $\{0,1,2,3,4\}$; the edge $ij$ is written $ij$. The value $16$ does not occur; the value $25$ first occurs on six vertices.} \label{tab:n5} \end{table} \begin{corollary}\label{cor:upto16} The values of $c$ on connected graphs that are at most $16$ are $1$, $3$, $6$, $7$ and the integers from $10$ to $15$. \end{corollary} \begin{proof} Graphs with at least six vertices have $c\ge21$ by Lemma~\ref{lem:rules}(f). Apply Lemma~\ref{lem:upto4}, Proposition~\ref{prop:no16} and the bound $c\ge15$ for five vertices. \end{proof} \section{Every integer at least seventeen}\label{sec:large} The construction works with all graphs, not only connected ones. The reason is the cone of Lemma~\ref{lem:rules}(d). If $H$ has $m-1$ vertices and $c(H)=x$, then the cone over $H$ is a connected graph on $m$ vertices with $c=2^{m-1}+x$. So the natural auxiliary object is the set $\Lam_m$ of values of $c$ on all graphs with $m$ vertices. Cones alone do not suffice. Every graph on $m-1$ vertices has at least $m-1$ connected sets, its singletons, so cones give only values $2^{m-1}+x$ with $x\ge m-1$. They miss the $m-1$ values from $2^{m-1}$ to $2^{m-1}+m-2$, at the bottom of the interval $[2^{m-1},2^m-1]$. The near-cones defined below fill this gap. \subsection{Three rules and seven small graphs} \begin{definition}\label{def:nearcone} Let $d\ge1$, $r\ge0$, and let $R$ be a graph with $r$ vertices. The \emph{near-cone} $N(d,R)$ is obtained as follows: take a star $K_{1,d}$ with centre $u$ and leaves $\ell_1,\dots,\ell_d$ and a disjoint copy of $R$, and add a vertex $w$ adjacent to every vertex except $u$ (Figure~\ref{fig:nearcone}). Formally, its vertices are $u$, $\ell_1,\dots,\ell_d$, $w$ and the vertices of $R$, and its edges are those of $R$, the edges $u\ell_t$ and $w\ell_t$ for $1\le t\le d$, and the edges joining $w$ to every vertex of $R$. Thus $N(d,R)$ is connected and has $m=d+r+2$ vertices. \end{definition} \begin{figure}[ht] \centering \begin{tikzpicture}[v/.style={circle,fill,inner sep=1.5pt}] \node[v,label=left:$u$] (u) at (0,0) {}; \node[v,label=above:$\ell_1$] (l1) at (1.6,1.1) {}; \node[v,label=above:$\ell_2$] (l2) at (1.6,0.4) {}; \node at (1.6,-0.25) {$\vdots$}; \node[v,label=below:$\ell_d$] (ld) at (1.6,-1.1) {}; \node[v,label=above:$w$] (w) at (3.2,0) {}; \draw (5.2,0) ellipse (1.1 and 0.9); \node at (5.6,0.55) {$R$}; \foreach \y [count=\i] in {0.5,0.1,-0.3,-0.6} {\node[v] (r\i) at (4.75,\y) {}; \draw (w)--(r\i);} \foreach \l in {l1,l2,ld} {\draw (u)--(\l)--(w);} \draw[dotted,gray] (u) .. controls (1.6,-2.0) and (2.6,-1.3) .. (w); \node[gray] at (2.5,-1.85) {\footnotesize no edge}; \end{tikzpicture} \caption{The near-cone $N(d,R)$. The vertex $w$ is joined to $\ell_1,\dots,\ell_d$ and to every vertex of $R$; the centre $u$ of the star is joined only to the $\ell_t$.} \label{fig:nearcone} \end{figure} \begin{lemma}\label{lem:threerules} Let $m\ge1$. \begin{enumerate}[label=\textup{(\Alph*)}] \item[\textup{(U)}] If $x\in V_a$ and $y\in\Lam_{m-a}$ with $1\le a\le m$, then $x+y\in\Lam_m$. In particular $\Lam_{m-1}+1\subseteq\Lam_m$. \item[\textup{(C)}] $2^{m-1}+\Lam_{m-1}\subseteq V_m$. \item[\textup{(N)}] If $d\ge1$, $r\ge0$ and $d+r+2=m$, then $2^{m-1}-2^r+2^d+d+\Lam_r\subseteq V_m$. More precisely, \[ c(N(d,R))=2^{m-1}-2^r+2^d+d+c(R). \] \end{enumerate} \end{lemma} \begin{proof} (U) is Lemma~\ref{lem:rules}(a) (add a disjoint connected graph, for instance an isolated vertex), and (C) is Lemma~\ref{lem:rules}(d). For (N), let $G=N(d,R)$ and count its connected sets according to whether they contain $w$. The connected sets avoiding $w$ are those of $G-w=K_{1,d}\sqcup R$; there are $2^d+d+c(R)$ of them, by Lemma~\ref{lem:rules}(a) and Example~\ref{ex:formulas}(i). The sets containing $w$ are the $2^{m-1}$ sets $\{w\}\cup U$ with $U\subseteq V(G)\setminus\{w\}$. Since $w$ is adjacent to every vertex other than $u$, and $u$ is adjacent only to the leaves, such a set is disconnected exactly when $U$ contains $u$ but no leaf $\ell_t$. There are $2^r$ such sets $U$: they contain $u$, no leaf, and an arbitrary set of vertices of $R$. Hence $c(G)=2^d+d+c(R)+2^{m-1}-2^r$. This is also the case $K=K_{1,d}\sqcup R$ of Lemma~\ref{lem:rules}(e). \end{proof} \begin{lemma}\label{lem:sporadic} The seven graphs of Table~\ref{tab:sporadic} and Figure~\ref{fig:sporadic} have the stated values. Hence $19\in V_5$; $25,32,35,57\in V_6$; and $67,90\in V_7$. \end{lemma} \begin{table}[ht] \centering \small \begin{tabular}{r c p{7.3cm} p{4.6cm}} \toprule $c$ & $m$ & graph & count\\ \midrule 19 & 5 & triangle $xyz$ with one pendant vertex at $x$ and one at $y$ & Ex.~\ref{ex:formulas}(ii): $3\cdot3\cdot2-1+2$\\ 32 & 6 & triangle $xyz$ with two pendant vertices at $x$ and one at $y$ & Ex.~\ref{ex:formulas}(ii): $5\cdot3\cdot2-1+3$\\ 35 & 6 & $K_4$ minus an edge $ab$, with one pendant vertex at $a$ and one at a vertex $z$ of degree $3$ & see the proof\\ 57 & 6 & $K_6$ minus two disjoint paths with three vertices each & Ex.~\ref{ex:formulas}(iii): $63-3-3$\\ 67 & 7 & $K_{2,3}$ with two pendant vertices at a vertex $x$ of the larger side & Lem.~\ref{lem:rules}(c): $13\cdot4+13+2$\\ 90 & 7 & $K_6$ minus two edges $va$, $vb$, with a pendant vertex at $v$ & Lem.~\ref{lem:rules}(c): $29\cdot2+31+1$\\ \midrule 25 & 6 & spider with legs of lengths $1$, $2$, $2$ & Ex.~\ref{ex:formulas}(i): $2\cdot3\cdot3+1+3+3$\\ \bottomrule \end{tabular} \caption{The sporadic graphs, drawn in Figure~\ref{fig:sporadic}. The six graphs above the line fill the gaps left by the rules (U), (C) and (N) in Lemma~\ref{lem:base} (Remark~\ref{rem:sharpbase}). The spider below the line realizes $25$ on six vertices (Corollary~\ref{cor:all17}).} \label{tab:sporadic} \end{table} \begin{figure}[ht] \centering \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (x) at (0.000,0.000) {}; \node[v] (y) at (1.000,0.000) {}; \node[v] (z) at (0.500,0.850) {}; \node[v] (p1) at (-0.600,-0.400) {}; \node[v] (p2) at (1.600,-0.400) {}; \draw (x)--(y) (x)--(z) (y)--(z) (x)--(p1) (y)--(p2); \node[below] at (x) {\footnotesize$x$}; \node[below] at (y) {\footnotesize$y$}; \node[above] at (z) {\footnotesize$z$}; \end{tikzpicture} \\[2pt]{\small $c=19$, $m=5$} \end{minipage}\hfill \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (x) at (0.000,0.000) {}; \node[v] (y) at (1.000,0.000) {}; \node[v] (z) at (0.500,0.850) {}; \node[v] (p1) at (-0.600,-0.450) {}; \node[v] (p2) at (-0.600,0.350) {}; \node[v] (p3) at (1.600,-0.400) {}; \draw (x)--(y) (x)--(z) (y)--(z) (x)--(p1) (x)--(p2) (y)--(p3); \node[below] at (x) {\footnotesize$x$}; \node[below] at (y) {\footnotesize$y$}; \node[above] at (z) {\footnotesize$z$}; \end{tikzpicture} \\[2pt]{\small $c=32$, $m=6$} \end{minipage}\hfill \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (a) at (0.000,0.500) {}; \node[v] (b) at (1.200,0.500) {}; \node[v] (z) at (0.600,1.100) {}; \node[v] (t) at (0.600,-0.100) {}; \node[v] (pa) at (-0.600,0.500) {}; \node[v] (pz) at (0.600,1.700) {}; \draw (a)--(z) (a)--(t) (b)--(z) (b)--(t) (z)--(t) (a)--(pa) (z)--(pz); \node[above left] at (a) {\footnotesize$a$}; \node[right] at (b) {\footnotesize$b$}; \node[right] at (z) {\footnotesize$z$}; \end{tikzpicture} \\[2pt]{\small $c=35$, $m=6$} \end{minipage}\hfill \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (h0) at (0.000,0.750) {}; \node[v] (h1) at (-0.650,0.375) {}; \node[v] (h2) at (-0.650,-0.375) {}; \node[v] (h3) at (-0.000,-0.750) {}; \node[v] (h4) at (0.650,-0.375) {}; \node[v] (h5) at (0.650,0.375) {}; \draw (h0)--(h2) (h0)--(h3) (h0)--(h4) (h0)--(h5) (h1)--(h3) (h1)--(h4) (h1)--(h5) (h2)--(h3) (h2)--(h4) (h2)--(h5) (h3)--(h5); \end{tikzpicture} \\[2pt]{\small $c=57$, $m=6$} \end{minipage} \\[10pt] \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (p) at (0.300,1.000) {}; \node[v] (q) at (1.300,1.000) {}; \node[v] (x) at (-0.200,0.000) {}; \node[v] (y) at (0.800,0.000) {}; \node[v] (w) at (1.800,0.000) {}; \node[v] (s1) at (-0.700,-0.600) {}; \node[v] (s2) at (0.300,-0.600) {}; \draw (p)--(x) (p)--(y) (p)--(w) (q)--(x) (q)--(y) (q)--(w) (x)--(s1) (x)--(s2); \node[above] at (p) {\footnotesize$p$}; \node[above] at (q) {\footnotesize$q$}; \node[right] at (x) {\footnotesize$x$}; \end{tikzpicture} \\[2pt]{\small $c=67$, $m=7$} \end{minipage}\hfill \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (v) at (0.000,0.850) {}; \node[v] (a) at (-0.750,0.400) {}; \node[v] (b) at (0.750,0.400) {}; \node[v] (c) at (-0.750,-0.450) {}; \node[v] (d) at (0.000,-0.850) {}; \node[v] (e) at (0.750,-0.450) {}; \node[v] (pv) at (0.000,1.550) {}; \draw (v)--(c) (v)--(d) (v)--(e) (a)--(b) (a)--(c) (a)--(d) (a)--(e) (b)--(c) (b)--(d) (b)--(e) (c)--(d) (c)--(e) (d)--(e) (v)--(pv); \node[left] at (v) {\footnotesize$v$}; \node[left] at (a) {\footnotesize$a$}; \node[right] at (b) {\footnotesize$b$}; \end{tikzpicture} \\[2pt]{\small $c=90$, $m=7$} \end{minipage}\hfill \begin{minipage}[b]{0.24\textwidth}\centering \begin{tikzpicture}[scale=1.0,v/.style={circle,fill,inner sep=1.4pt}] \node[v] (o) at (0.000,0.000) {}; \node[v] (l1) at (0.000,0.700) {}; \node[v] (m1) at (-0.600,-0.350) {}; \node[v] (m2) at (-1.200,-0.700) {}; \node[v] (n1) at (0.600,-0.350) {}; \node[v] (n2) at (1.200,-0.700) {}; \draw (o)--(l1) (o)--(m1) (m1)--(m2) (o)--(n1) (n1)--(n2); \end{tikzpicture} \\[2pt]{\small $c=25$, $m=6$} \end{minipage} \caption{The seven sporadic graphs of Table~\ref{tab:sporadic}, with their values of $c$ and their numbers $m$ of vertices. In the graph with $c=57$, the hexagon is drawn without four of its sides; these form the two removed paths with three vertices each.} \label{fig:sporadic} \end{figure} \begin{proof} The values $19$, $25$, $32$ and $57$ follow from Example~\ref{ex:formulas}; for $57$, $\Phi$ consists of two copies of $K_{1,2}$. For $c=35$: a connected set is either one of the two pendant vertices, or a connected set $Q$ of $K_4-ab$ together with any of the pendant vertices attached at $Q$. The connected sets of $K_4-ab$ are all nonempty subsets of its vertex set other than $\{a,b\}$, hence $14$ sets. Summing $2^{|Q\cap\{a,z\}|}$ over all nonempty $Q$ gives $3\cdot3\cdot2\cdot2-1=35$; removing $Q=\{a,b\}$ subtracts $2$, and the pendant vertices add $2$, giving $35$. For $c=67$: glue $K_{2,3}$ and the star $K_{1,2}$ at $x$ (Lemma~\ref{lem:rules}(c)). Let $\{p,q\}$ be the smaller side and $\{x,y,z\}$ the larger one. The connected sets of $K_{2,3}$ containing $x$ are $\{x\}$ and the sets $\{x\}\cup S\cup S'$ with $\emptyset\ne S\subseteq\{p,q\}$ and $S'\subseteq\{y,z\}$; there are $1+3\cdot4=13$. Also $K_{2,3}-x=C_4$ has $c=13$, and the star contributes $c_x=4$ and $c(K_{1,2}-x)=2$. For $c=90$: let $H=K_6-va-vb$ and glue $H$ with an edge at $v$. In $H$, the sets containing $v$ that are disconnected are $\{v,a\}$, $\{v,b\}$ and $\{v,a,b\}$, so $c_v(H)=32-3=29$; and $H-v=K_5$ has $c=31$. The edge contributes $c_v=2$ and $1$. \end{proof} \subsection{The base} \begin{lemma}\label{lem:base} \begin{enumerate}[label=\textup{(\alph*)}] \item $\Lam_3\supseteq\{3,4,6,7\}$, $\Lam_4\supseteq[4,8]\cup[10,15]$, $\Lam_5\supseteq[5,24]\cup[26,31]$, $\Lam_6\supseteq[6,25]\cup[27,63]$ and $\Lam_7\supseteq[7,127]$. \item $V_5\supseteq[17,24]\cup[26,31]$, $V_6\supseteq[32,63]$ and $V_7\supseteq[64,127]$. \end{enumerate} \end{lemma} \begin{proof} We apply the rules of Lemma~\ref{lem:threerules}, starting from $V_1=\Lam_1=\{1\}$ and $\Lam_0=\{0\}$, one order at a time. At each order we use only the inclusions already established at smaller orders, and we record only inclusions. We give the order $m=5$ in full; Table~\ref{tab:base} lists every order. For $m=5$, the rule (C) applied to $\Lam_4\supseteq[4,8]\cup[10,15]$ gives $16+([4,8]\cup[10,15])=[20,24]\cup[26,31]$. The rule (N) with $(d,r)=(1,2)$ gives $2^4-2^2+2^1+1+\Lam_2\supseteq15+\{2,3\}=\{17,18\}$. The sporadic graph with $c=19$ (Lemma~\ref{lem:sporadic}) supplies the remaining value, so $V_5\supseteq[17,24]\cup[26,31]$. By (U), $\Lam_4+1\supseteq[5,9]\cup[11,16]$ and $7+3=10\in V_3+\Lam_2$. Together with $V_5$, this gives $\Lam_5\supseteq[5,24]\cup[26,31]$. \end{proof} \begin{table}[ht] \centering \footnotesize \newcolumntype{P}[1]{>{\raggedright\arraybackslash}p{#1}} \begin{tabular}{c P{3.0cm} P{3.7cm} c P{1.7cm} P{3.4cm}} \toprule $m$ & cones (C) & near-cones (N), with $(d,r)$ & sporadic & $V_m\supseteq$ & $\Lam_m\supseteq$ by (U) and $V_m$\\ \midrule 2 & $2+\{1\}=\{3\}$ & --- & --- & $\{3\}$ & $\{1\}+1$; so $\{2,3\}$\\ 3 & $4+\{2,3\}=\{6,7\}$ & --- & --- & $\{6,7\}$ & $\{2,3\}+1$; so $\{3,4,6,7\}$\\ 4 & $8+\{3,4,6,7\}=\{11,12,14,15\}$ & $(1,1)$: $10$; $(2,0)$: $13$ & --- & $[10,15]$ & $\{3,4,6,7\}+1$, $3+3$; so $[4,8]\cup[10,15]$\\ 5 & $16+\Lam_4$: $[20,24]\cup[26,31]$ & $(1,2)$: $15+\{2,3\}=\{17,18\}$ & $19$ & $[17,24]\cup[26,31]$ & $[5,9]\cup[11,16]$, $7+3$; so $[5,24]\cup[26,31]$\\ 6 & $32+\Lam_5$: $[37,56]\cup[58,63]$ & $(1,3)$: $27+\{3,4,6,7\}=\{30,31,33,34\}$; $(2,2)$: $34+\{2,3\}=\{36,37\}$ & $32,35,57$ & $[32,63]$ & $[6,25]\cup[27,32]$; so $[6,25]\cup[27,63]$\\ 7 & $64+\Lam_6$: $[70,89]\cup[91,127]$ & $(1,4)$: $51+[13,15]=[64,66]$; $(2,3)$: $62+\{6,7\}=\{68,69\}$ & $67,90$ & $[64,127]$ & $[7,26]\cup[28,64]$, $24+3$; so $[7,127]$\\ \bottomrule \end{tabular} \caption{The steps of the proof of Lemma~\ref{lem:base}. In the cone and near-cone columns, $\Lam_r$ stands for the part of $\Lam_r$ established in the previous rows. The column (U) lists $\Lam_{m-1}+1$ and the sums $x+y$ with $x\in V_a$, $y\in\Lam_{m-a}$ that are needed; for instance $3+3\in V_2+\Lam_2$ and $24+3\in V_5+\Lam_2$.} \label{tab:base} \end{table} \begin{remark}\label{rem:sharpbase} Two statements must be distinguished here: a value may fail to be produced by the rules (C) and (N), and a value may fail to be realized by any graph. Lemma~\ref{lem:base} is sharp in the second sense: $5\notin\Lam_3$, $9\notin\Lam_4$, $25\notin\Lam_5$, $26\notin\Lam_6$ and $16,25\notin V_5$, by the computation of Section~\ref{sec:computation}. In the first sense, even with every sporadic graph of smaller order available, the rules (C) and (N) produce on five vertices every value in $[17,31]$ except $19$ and $25$, on six vertices every value in $[32,63]$ except $32$, $35$ and $57$, and on seven vertices every value in $[64,127]$ except $67$ and $90$ (Section~\ref{sec:computation}). All these values except $25$ do lie in $V_m$, and the six sporadic graphs above the line in Table~\ref{tab:sporadic} realize them. The remaining sporadic graph realizes $25$ on six vertices. \end{remark} \subsection{The induction} \begin{theorem}\label{thm:dyadic} For every $m\ge8$: \begin{enumerate}[label=\textup{(\roman*)}] \item[$(\mathrm G_m)$] $V_m\supseteq[2^{m-1},2^m-1]$; \item[$(\mathrm H_m)$] $\Lam_m\supseteq[m,2^m-1]$. \end{enumerate} Together with Lemma~\ref{lem:base}, $(\mathrm G_m)$ holds for all $m\ge6$ and $(\mathrm H_m)$ for all $m\ge7$. \end{theorem} The two assertions play different roles. The assertion $(\mathrm H_m)$ provides auxiliary graphs, possibly disconnected, with every count from $m$ to $2^m-1$; the assertion $(\mathrm G_m)$ provides connected graphs for the upper half of the range. We prove $(\mathrm G_m)$ from earlier $(\mathrm H)$-statements, and then obtain $(\mathrm H_m)$ by combining $(\mathrm G_m)$ with the isolated-vertex rule (U). In the proof of $(\mathrm G_m)$ the interval splits as \[ [2^{m-1},2^m-1]=\underbrace{[2^{m-1},\,2^{m-1}+m-2]}_{\text{near-cones}}\ \cup\ \underbrace{[2^{m-1}+m-1,\,2^m-1]}_{\text{cones}}. \] \begin{proof} We use induction on $m\ge8$. Assume $(\mathrm H_{m'})$ for $7\le m'