Degree-sequence reconstruction from a partial deck with a constant number of missing cards (Groenland–Guggiari–Scott conjecture)

The deck of a graph $G$ on $n$ vertices is the multiset of its $n$ vertex-deleted subgraphs (cards), and the degree sequence of $G$ is the non-increasing list of vertex degrees. Myrvold showed in 1992 that the degree sequence is determined by any deck missing one card, and Groenland, Guggiari and Scott conjectured in 2018 (published 2021) that this persists for any fixed number $k$ of missing cards: for every fixed $k$ and all sufficiently large $n$ , the degree sequence of any $n$ -vertex graph is reconstructible from any $n-k$ of its cards. The 2022 paper of Groenland, Johnston, Kupavskii, Meeks, Scott and Tan that records this conjecture verifies it only for graphs of average degree at most $c_k n^{1/3}$ , and the general case remains open. The problem is to prove or refute the conjecture for unrestricted graphs. The same 2022 paper's companion open question — how many cards two distinct $n$ -vertex graphs can share — was resolved in 2026 by Ivanov, who showed the shared fraction can be arbitrarily close to the whole deck (refuting the Bowler–Brown–Fenner conjecture), but all of Ivanov's pairs share the same degree sequence, leaving the degree-sequence conjecture untouched.

Background

All graphs here are finite, simple and undirected. For a graph $G$ on $n$ vertices, the card $G-v$ is the unlabelled subgraph obtained by deleting the vertex $v$ and its incident edges, and the deck $D(G)$ is the multiset of all $n$ cards. The Reconstruction Conjecture of Kelly and Ulam asserts that every graph with at least three vertices is determined up to isomorphism by its full deck; it remains open. A weaker and partially tractable line asks which individual parameters of $G$ are determined by the deck or by parts of it. The degree sequence of $G$ is the multiset of its vertex degrees; knowing it determines, for example, the number of edges. Kelly's Lemma (1957) states that for graphs $|H|<|G|$ , the number of subgraphs of $G$ isomorphic to $H$ is reconstructible from the full deck. Partial-deck versions ask what can be recovered when some cards are missing. Myrvold (1992) proved that for $n\ge 7$ the degree sequence is reconstructible from any $n-1$ cards (a deck missing one card). For the coarser invariant of edge count, Brown and Fenner (2018) proved reconstructibility from any $n-2$ cards for $n\ge 29$ , and Groenland, Guggiari and Scott (2021) proved that for all sufficiently large $n$ the number of edges is reconstructible from any $n-k$ cards whenever $k\le\tfrac{1}{20}\sqrt{n}$ ; in the same paper they conjectured (their Conjecture 3.3) that the same holds for the degree sequence with any fixed $k$ . Progress towards this came from Groenland, Johnston, Kupavskii, Meeks, Scott and Tan (2022): they proved that a graph of average degree $d$ has its degree sequence reconstructible from any deck missing at most $O(n/d^{3})$ cards, so that in particular the conjecture holds for graphs of average degree at most $c_k n^{1/3}$ for a constant $c_k$ depending only on $k$ , and that graphs embeddable on any fixed surface (such as planar graphs, which have bounded average degree) admit reconstruction of the degree sequence from a suitable linear fraction $(1-\varepsilon)n$ of the cards. However, the general case — arbitrary graphs with any fixed number $k\ge 2$ of missing cards — remained (and remains) open. Related later work: Knierim and Martinsson (2021/2024) showed the number of $r$ -cliques is reconstructible from any $n-1$ cards for all but at most one value of $r$ , and for all $r\le\log_2 n$ ; this handles clique counts for $k=1$ but not the degree sequence for $k\ge 2$ . A complementary extremal quantity is $cc(n)$ , the maximum number of common cards shared by two distinct (non-isomorphic) $n$ -vertex graphs. Bowler, Brown and Fenner (2010) constructed pairs with $cc(n)\ge(\tfrac{2}{3}+o(1))n$ and conjectured that, for large $n$ , every graph is determined by any $2\lfloor(n-1)/3\rfloor+1$ of its cards. Ivanov (2026) refuted this: he gave an explicit connected non-isomorphic pair on 78 vertices with at least 51 common cards (exceeding the predicted $50$ ), and constructed, for every even $r\ge 4$ , families at arbitrarily large orders whose decks share an asymptotic fraction at least $1-1/r$ of their cards, so that $\limsup cc(n)/n=1$ . Notably, all of Ivanov's pairs have the same degree sequence, so his construction is consistent with — and highlights — the degree-sequence conjecture above: two graphs whose degree sequences differ must eventually be distinguishable from all but $k$ of their cards if the conjecture is true.

Problem Statement

Prove or refute the following conjecture of Groenland, Guggiari and Scott (Conjecture 3.3 of 'Size reconstructibility of graphs', Journal of Graph Theory 96(2):326–337, 2021, arXiv:1807.11733; restated as Conjecture 10 in 'Reconstructing the degree sequence of a sparse graph from a partial deck', 2022): for every fixed positive integer $k$ there exists $n_0(k)$ such that for all $n\ge n_0(k)$ , the degree sequence of every $n$ -vertex graph $G$ is determined by any multiset of $n-k$ cards from its deck $D(G)$ — that is, any other $n$ -vertex graph whose deck contains those same $n-k$ cards has the same degree sequence as $G$ . Equivalently (as a common-card bound): for all $n\ge n_0(k)$ , any two non-isomorphic $n$ -vertex graphs whose degree sequences differ share at most $n-k-1$ cards, counting multiplicity. The conjecture is currently verified only for $k=1$ (all graphs, by Myrvold) and for arbitrary fixed $k$ under a sparsity constraint (average degree at most $c_k n^{1/3}$ , by Groenland–Johnston–Kupavskii–Meeks–Scott–Tan); the problem asks for the unrestricted statement, with no constraint on the graph beyond the number of vertices.

References

Carla Groenland, Tom Johnston, Andrey Kupavskii, Kitty Meeks, Alex Scott, Jane Tan. Reconstructing the degree sequence of a sparse graph from a partial deck. Journal of Combinatorial Theory, Series B 157:283–293, 2022. DOI: 10.1016/j.jctb.2022.07.004; arXiv:2102.08679. https://arxiv.org/abs/2102.08679
Carla Groenland, Hannah Guggiari, Alex Scott. Size reconstructibility of graphs. Journal of Graph Theory 96(2):326–337, 2021. DOI: 10.1002/jgt.22616; arXiv:1807.11733. https://arxiv.org/abs/1807.11733
Sergey Ivanov. Nonisomorphic Graphs Can Share an Arbitrarily Large Fraction of Their Vertex-Deleted Cards. arXiv:2608.11930, 2026. https://arxiv.org/abs/2608.11930
Charlotte Knierim, Anders Martinsson. Reconstructibility of the $K_r$ -count from $n-1$ cards. Discrete Mathematics 347(6):113950, 2024. DOI: 10.1016/j.disc.2024.113950; arXiv:2112.03366. https://arxiv.org/abs/2112.03366
Andrew Bowler, Paul Brown, Trevor Fenner. Families of pairs of graphs with a large number of common cards. Journal of Graph Theory 63(2):146–163, 2010. DOI: 10.1002/jgt.20415. https://doi.org/10.1002/jgt.20415
Wendy Myrvold. The degree sequence is reconstructible from $n-1$ cards. Discrete Mathematics 102(2):187–196, 1992. DOI: 10.1016/0012-365X(92)90053-I. https://doi.org/10.1016/0012-365X(92)90053-I
Paul Brown, Trevor Fenner. The size of a graph is reconstructible from any $n-2$ cards. Discrete Mathematics 341(1):165–174, 2018. DOI: 10.1016/j.disc.2017.08.026. https://doi.org/10.1016/j.disc.2017.08.026
Carla Groenland, Tom Johnston, Alex Scott, Jane Tan. Reconstruction from smaller cards. Israel Journal of Mathematics 273(2):823–860, 2026. DOI: 10.1007/s11856-025-2858-3; arXiv:2103.13359. https://arxiv.org/abs/2103.13359