Reconstructibility of the K-count from n − 1 cards

The Reconstruction Conjecture of Kelly and Ulam states that any graph G with n≥3 vertices can be reconstructed from the multiset D(G) of unlabelled subgraphs G−v for all v∈V(G). We refer to D(G) as the deck of G and G−v∈D(G) as the cards of G. This was posed in the 1940s and is still wide open today. In an effort to understand reconstructibility better, a growing collection of research is concerned with understanding what properties of G can be reconstructed from a (potentially adversarially chosen) collection of k cards for some k<n. In this paper, we show that the clique count of G is reconstructible for all but one size of clique from any n−1 cards. We extend this result by showing that for graphs with average degree at most 3n/8−O(1) we can reconstruct the Kr-count for all r, and that for r≤log2⁡n we can reconstruct the Kr-count for every graph on n vertices.