Reconstructibility of the \(K_r\)-count from \(n - 1\) cards (Q6494931)

Let \(G\) be a graph on \(n\) vertices. It is a well-known result by \textit{P. J. Kelly} [Pac. J. Math. 7, 961--968 (1957; Zbl 0078.37103)] that, for any subgraph \(H\) on less than \(n\) vertices, the number of copies of \(H\) contained in \(G\) can be reconstructed from the multiset (also called the deck) of \(n\) unlabelled one-vertex deleted subgraphs (also called the cards). Let \(n\geq 7\). The authors prove that, with \(\ell \) denoting the number of vertices of maximum degree, the number of copies of the complete graph \(K_r \) on \(r\not= n-\ell \) vertices in \(G\) can be reconstructed from any \(n-1\) cards. Moreover, for \(r\leq \log _2 (n)\), the number of copies of \(K_r \) can always be reconstructed from any \(n-1\) cards, and, for graphs with average degree \(\leq \frac{3n}{8}-O(1)\), the condition \(r\not= n-\ell \) can be circumvented.NEWLINENEWLINEThe authors provide a summary of similar results, all of which certainly indicate the difficulty of the Reconstruction Conjecture.