  The deck of a graph $G$ is the multiset of cards $\{G-v:v\in V(G)\}$. Myrvold
(1992) showed that the degree sequence of a graph on $n\geq7$ vertices can be
reconstructed from any deck missing one card. We prove that the degree sequence
of a graph with average degree $d$ can reconstructed from any deck missing
$O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on
a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed
even when a linear number of the cards are missing.

Combinatorics