Nýdl's reconstructibility conjecture for trees

For an nn-vertex graph, the mm-deck is the multiset of its unlabeled induced mm-vertex subgraphs, and a family of graphs is weakly celltextellcelltext{ell}-reconstructible if no two graphs in the family have the same (ncelltextell)(n-celltext{ell})-deck. Nýdl's conjecture. For ncellge2celltextell+1ncellge 2celltext{ell}+1, no two nn-vertex trees have the same (ncelltextell)(n-celltext{ell})-deck; equivalently, trees with at least 2celltextell+12celltext{ell}+1 vertices are weakly celltextellcelltext{ell}-reconstructible. The conjecture is refuted by two 1313-vertex trees with the same 77-deck, although the stated bound is sharp in general because examples with 2celltextell2celltext{ell} vertices and the same celltextellcelltext{ell}-deck are known.

Sources & referencesView supporting material

Primary source

Alexandr V. Kostochka, Zishen Qu, Maddy Ritter and Douglas B. West, “Caterpillars with n vertices are reconstructible from subgraphs with at most n/2+1 vertices”, arXiv:2511.23309 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.