Graph reconstruction from connected $k$-sets: strong $T_k$-reconstructibility for $k \ge 4$, class-level criteria, and minimality of the $T_3$ characterization

Bastide et al. (WG 2023) introduced a graph-reconstruction model in which the only information about an unknown labeled graph $G$ is $T_k(G)$, the family of $k$-vertex subsets that induce connected subgraphs. Qi (arXiv 2023; Discrete Mathematics 2026) completed the 'strong' theory at $k = 3$ by characterizing exactly which graphs are uniquely determined among all graphs by their connected triples $T_3$: twin-free graphs in which every edge lying in a triangle sits in one of six explicit local configuration families. The objective is to resolve the questions Qi's paper explicitly leaves open: (i) whether the six families in that characterization are minimal, or whether an equivalent characterization exists with a strictly smaller or different finite family list; (ii) the higher-order analogue, namely a characterization of strongly $T_k$-reconstructible graphs for $k \ge 4$; and (iii) necessary and sufficient conditions on a graph class for $T_3$-reconstructibility, extended to arbitrary $k$. Later work (Kluk, La, and Piecyk, WG 2024) advanced the class-level and algorithmic picture — uniqueness of large triangle-free graphs for all $k > 3$, polynomial enumeration algorithms, and NP-hardness of a partial-information variant — but none of the three questions has been resolved in the literature to date.

Background

A classic theme in graph theory is reconstruction: how much partial information about an unknown graph suffices to recover it? The best-known instance is the classical Reconstruction Conjecture, which asks whether every graph is determined up to isomorphism by the multiset of its vertex-deleted subgraphs; it remains open. Bastide, Cook, Erickson, Groenland, van Kreveld, Mannens, and Vermeulen introduced a different, information-poorer model, motivated by settings in which only local connectivity of a network is observable. For an integer $k \ge 2$ and a finite, simple, connected graph $G$ on a labeled vertex set (each vertex carries a distinguishing name, so two graphs are 'equal' only if their edge sets are identical, not merely isomorphic), the set of connected $k$-sets is

$T_k(G) := \{X \subseteq V(G) : |X| = k \text{ and } G[X] \text{ is connected}\},$

where $G[X]$ is the subgraph induced by $X$, i.e., all edges of $G$ with both ends in $X$. For $k = 2$ this is exactly the edge set, so nothing is lost; for $k = 3$ the elements of $T_3(G)$ are the connected triples — 3-subsets spanning either a triangle or a two-edge path.

Two uniqueness notions drive the theory. A graph $G$ is strongly $T_k$-reconstructible if every finite, simple, connected labeled graph $H$ with $T_k(H) = T_k(G)$ satisfies $H = G$ — uniqueness among all graphs, with no side information. A class $\mathcal{C}$ of graphs is $T_k$-reconstructible if whenever $G, H \in \mathcal{C}$ and $T_k(G) = T_k(H)$, then $G = H$ — uniqueness only within the class, which is a strictly weaker demand since knowing the unknown graph lies in $\mathcal{C}$ can rescue uniqueness.

Bastide et al. showed that almost every graph can be uniquely reconstructed from its connected triples; gave an $O(n \cdot |T|)$ algorithm, via reduction to 2-SAT, that returns a graph consistent with a given set $T$ of connected triples and decides uniqueness; and proved $T_3$-reconstructibility for the classes of trees on at least five vertices, triangle-free graphs (graphs containing no 3-cycle), 2-connected outerplanar graphs (graphs embeddable in the plane with every vertex on the outer face), and maximal planar graphs (plane triangulations). For general $k$ they proved that $n$-vertex trees are pairwise distinguished by their connected $k$-sets exactly up to $k = \lceil n/2 \rceil$, and that every graph on at least $2k - 1$ vertices with no cycle of length at most $k$ is determined by its connected $k$-sets. A basic obstruction observed throughout this literature is that of twin vertices: two distinct vertices $u, v$ with $N(u) \setminus \{v\} = N(v) \setminus \{u\}$, where $N(\cdot)$ is the open neighborhood, can never be told apart as to whether they are adjacent, so graphs containing twins are never strongly $T_k$-reconstructible.

Qi then completed the strong theory at $k = 3$. Call an edge of $G$ necessary if it is present in every graph with the same $T_3$. Qi's main theorem states that a graph $G$ on $n \ge 5$ vertices is strongly $T_3$-reconstructible if and only if (i) no two distinct vertices of $G$ are twins as above, and (ii) every edge of $G$ that lies in a triangle is contained in an induced subgraph belonging to one of six explicitly drawn families $F_1, \ldots, F_6$ of small local configurations (Figure 4 of the paper), each of which forces its distinguished edge to be necessary. The proof of necessity reduces, via Burnside's lemma applied to the possible neighborhood patterns of a triangle, to twelve cases. On the class level, Qi proved that regular planar graphs on at least 7 vertices, 5-connected planar graphs, strongly regular graphs — graphs in which every vertex has degree $k$, every adjacent pair has $\lambda$ common neighbors, and every non-adjacent pair has $\mu$ common neighbors — with parameters satisfying $2k - \lambda \ne \mu + 2$ and $v \ne 2k + 1$, and complete multipartite graphs are all $T_3$-reconstructible; whereas the class of $k$-connected planar graphs for $k \le 4$, Eulerian graphs (all vertex degrees even), and Hamiltonian graphs are not.

Most recently, Kluk, La, and Piecyk studied the model for general $k$ from an algorithmic angle: for every $k > 3$, every sufficiently large connected triangle-free graph is uniquely reconstructible within the class of triangle-free graphs; for any $k > 2$, the consistent triangle-free graphs, and the consistent graphs of bounded maximum degree, can be enumerated in time polynomial in the input and output size, with the bounded-degree solutions all sharing a common 'skeleton' and differing only locally; and deciding consistency becomes NP-hard for $k > 4$ in a variant where the connectivity of only some $k$-sets is specified. They suspect the general problem is NP-hard for large $k$.

The picture after this work: the strong theory is complete exactly at $k = 3$, the class-level theory is a growing but unstructured list of positive and negative examples, and nothing is known about whether the six families of the $k = 3$ characterization can be reduced. These are precisely the gaps that Qi's closing section poses as future work, stated below.

Problem Statement

The questions are those posed in Section 5 of Qi's paper. Throughout, $G$ ranges over finite, simple, connected graphs on a labeled vertex set; $T_k(G)$ is the family of $k$-subsets of $V(G)$ inducing a connected subgraph; $G$ is strongly $T_k$-reconstructible if every such graph $H$ with $T_k(H) = T_k(G)$ equals $G$; and a class $\mathcal{C}$ is $T_k$-reconstructible if any two members of $\mathcal{C}$ with the same $T_k$ are equal. The common objective of the three questions is a complete uniqueness theory for connected-$k$-set data: they respectively sharpen, extend, and broaden the same characterization program, whose $k = 3$ strong case is now settled.

(Q1) Minimality of the $k = 3$ characterization. In Qi's theorem — a graph $G$ on $n \ge 5$ vertices is strongly $T_3$-reconstructible if and only if $N(v_1) \setminus \{v_2\} \ne N(v_2) \setminus \{v_1\}$ for all distinct $v_1, v_2 \in V(G)$, and every edge of $G$ contained in a triangle lies in an induced subgraph belonging to one of the six families $F_1, \ldots, F_6$ of Figure 4 of Qi's paper, each family being a small local configuration that forces its distinguished edge to be necessary (present in every graph with the same $T_3$) — is the collection of six families minimal, i.e., is each family essential to the equivalence? Does an equivalent characterization exist with a strictly smaller or different finite family list, or in some other form altogether?

(Q2) Strong reconstructibility at higher order. Characterize the strongly $T_k$-reconstructible graphs for $k \ge 4$: for each $k \ge 4$ (the first open case is $k = 4$), determine exactly which graphs are uniquely determined among all graphs by their connected $k$-sets, in the spirit of the $k = 3$ theorem. A characterization for a single fixed $k$ is genuine progress; the question in full asks for arbitrary $k \ge 4$.

(Q3) Class-level criteria. Find necessary and sufficient conditions, in structural or otherwise checkable terms, on a graph class $\mathcal{C}$ for $\mathcal{C}$ to be $T_3$-reconstructible, and extend such a criterion to arbitrary $k$: for a given $k \ge 2$, determine which graph classes are $T_k$-reconstructible. The literature provides positive classes (trees, triangle-free, 2-connected outerplanar, maximal planar, regular planar on at least 7 vertices, 5-connected planar, certain strongly regular, complete multipartite, high-girth) and negative classes ($k$-connected planar for $k \le 4$, Eulerian, Hamiltonian) but no overarching criterion; an acceptable criterion must be equivalent to the stated uniqueness property — not merely a sufficient condition verified on known examples — and must be stated in structural or otherwise checkable terms, not obtained by restating that defining uniqueness property.

These questions are linked: (Q1) sharpens the completed $k = 3$ strong theory, (Q2) extends that theory to higher-order data, and (Q3) asks when restricting the comparison class rescues uniqueness for graphs — such as those containing twins — that fail strong reconstructibility. The three sub-questions are independent and may be attacked separately. Answers must hold in the stated generality (all graphs on $n \ge 5$ vertices in (Q1), all $k \ge 4$ in (Q2), all graph classes in (Q3)), without added restrictions to particular sizes, classes, or answer forms; in particular, a characterization for a single fixed $k \ge 4$ is genuine partial progress on (Q2), but (Q2) is resolved in full only by a characterization covering all $k \ge 4$.

References

1. Yaxin Qi, Graph Reconstruction from Connected Triples, arXiv:2309.10113 (2023), doi:10.48550/arXiv.2309.10113, https://arxiv.org/abs/2309.10113
2. Yaxin Qi, Graph reconstruction from connected triples, Discrete Mathematics 349, article 115058 (2026), doi:10.1016/j.disc.2026.115058, https://doi.org/10.1016/j.disc.2026.115058
3. Paul Bastide, Linda Cook, Jeff Erickson, Carla Groenland, Marc van Kreveld, Isja Mannens, Jordi L. Vermeulen, Reconstructing Graphs from Connected Triples, arXiv:2303.06609 (2023), doi:10.48550/arXiv.2303.06609, https://arxiv.org/abs/2303.06609
4. Paul Bastide, Linda Cook, Jeff Erickson, Carla Groenland, Marc van Kreveld, Isja Mannens, Jordi L. Vermeulen, Reconstructing Graphs from Connected Triples, International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023), Lecture Notes in Computer Science, Springer (2023), pp. 16-29, doi:10.1007/978-3-031-43380-1_2, https://doi.org/10.1007/978-3-031-43380-1_2
5. Kacper Kluk, Hoang La, Marta Piecyk, Graph Reconstruction with Connectivity Queries, arXiv:2407.07500 (2024), doi:10.48550/arXiv.2407.07500, https://arxiv.org/abs/2407.07500
6. Kacper Kluk, Hoang La, Marta Piecyk, Graph Reconstruction with Connectivity Queries, International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024), Lecture Notes in Computer Science, Springer (published 2025), pp. 343-357, doi:10.1007/978-3-031-75409-8_24, https://doi.org/10.1007/978-3-031-75409-8_24
7. Stijn Cambie, Carla Groenland, Note on extremal problems about connected subgraph sums, Graphs and Combinatorics 42:35 (2026), doi:10.1007/s00373-026-03026-8, https://doi.org/10.1007/s00373-026-03026-8