  We study a problem of reconstruction of connected graphs where the input
gives all subsets of size k that induce a connected subgraph. Originally
introduced by Bastide et al. (WG 2023) for triples ($k=3$), this problem
received comprehensive attention in their work, alongside a study by Qi, who
provided a complete characterization of graphs uniquely reconstructible via
their connected triples, i.e. no other graphs share the same set of connected
triples. Our contribution consists in output-polynomial time algorithms that
enumerate every triangle-free graph (resp. every graph with bounded maximum
degree) that is consistent with a specified set of connected $k$-sets. Notably,
we prove that triangle-free graphs are uniquely reconstructible, while graphs
with bounded maximum degree that are consistent with the same $k$-sets share a
substantial common structure, differing only locally. We suspect that the
problem is NP-hard in general and provide a NP-hardness proof for a variant
where the connectivity is specified for only some $k$-sets (with $k$ at least
4).
