The graph reconstruction conjecture (Kelly–Ulam) in its algebraic formulation: existence of full-rank covering-number matrices

The open question is stated in Oliveira and Thatte's 'An Algebraic Formulation of the Graph Reconstruction Conjecture' (J. Graph Theory 81(4):351–363, 2016). Writing $\psi(n)$ for the number of mutually nonisomorphic simple graphs on $n$ vertices and $d(n)$ for the number of distinct decks (multisets of vertex-deleted subgraphs) obtainable from them, the paper proves that the matrix of covering numbers produced from Kocay's lemma has rank at most $d(n)$ for every family of graph sequences, that a matrix of rank $\psi(n)$ would certify that all $n$-vertex graphs are reconstructible, and that rank exactly $d(n)$ is always attainable. The problem is therefore: for every $n\ge3$, construct a finite family of sequences of graphs on at most $n-1$ vertices whose covering-number matrix has rank $\psi(n)$, or prove that no such family exists for some $n$. By results proved in the paper this is equivalent to the graph reconstruction (Kelly–Ulam) conjecture.

Background

A (finite, simple, undirected) graph $G$ on $n$ vertices determines its deck, the multiset of its $n$ unlabelled vertex-deleted subgraphs $G-v$, each called a card. The graph reconstruction conjecture, one of the oldest open problems in graph theory and usually attributed to P. J. Kelly and S. M. Ulam, asserts that every graph on at least three vertices is reconstructible: any two graphs on at least three vertices with the same deck are isomorphic. The conjecture is known to hold for many special classes (for example trees, in work of Kelly), and a classical probabilistic result of Bollobás shows that almost every graph can be reconstructed from just three carefully chosen cards; but it is verified in full only for graphs on at most 13 vertices, by computer search (McKay 2022). The analogous statement is false for directed graphs: Stockmeyer constructed infinite families of non-reconstructible tournaments (1977) and of non-reconstructible digraphs (1981), which shows that any proof technique must use something specific to undirected simple graphs.

Two classical tools organize the information carried by a deck. Kelly's lemma states that for any graph $F$ with fewer vertices than $G$, the number $s(F,G)$ of subgraphs of $G$ isomorphic to $F$ is reconstructible, i.e., the same for all graphs with a given deck. Kocay's lemma extends this: for any sequence $F=(F_1,\dots,F_m)$ of graphs each on at most $n-1$ vertices, there exist constants $c(F,H)$, called covering numbers, such that the sum $\sum_H c(F,H)\cdot s(H,G)$, taken over all unlabelled $n$-vertex graphs $H$, is reconstructible. The constant $c(F,H)$ has a direct combinatorial meaning: it counts the number of ways to cover the graph $H$ by subgraphs isomorphic to $F_1,\dots,F_m$ whose union is all of $H$. Thus each sequence $F$ yields a linear constraint that every reconstruction of $G$ must satisfy.

Oliveira and Thatte quantify how much information such constraints can collectively carry. Let $\psi(n)$ be the number of mutually nonisomorphic graphs on $n$ vertices and $d(n)$ the number of distinct decks constructible from these graphs; then $\psi(n)-d(n)$ counts graphs that cannot be reconstructed from their decks, and the conjecture holds for $n$-vertex graphs if and only if $\psi(n)=d(n)$. For a finite family $\mathcal{F}$ of sequences they consider the real matrix $M_{\mathcal{F}}$ whose rows are indexed by the sequences of $\mathcal{F}$, whose columns are indexed by the isomorphism classes $H$ of $n$-vertex graphs, and whose $(F,H)$-entry is $c(F,H)$. They prove three things. First (Theorem 3.2), every such matrix satisfies $d(n)\ge\operatorname{rank}_{\mathbb{R}}(M_{\mathcal{F}})$: by Kocay's lemma, the difference of the subgraph-count profiles of two same-deck graphs lies in the nullspace of the matrix, so a rank–nullity argument bounds the rank by the number of decks. Second (Corollary 3.3), if some family yields a matrix of rank $\psi(n)$ (full column rank), then all $n$-vertex graphs are reconstructible. Third (Theorem 3.4), the family of all inequivalent sequences of length at most $n$ of $(n-1)$-vertex graphs attains rank exactly $d(n)$, so $d(n)$ is the maximum rank achievable and, if the conjecture holds for $n$-vertex graphs, a full-rank family necessarily exists. Consequently the conjecture is equivalent to the existence of a full-rank family, and a shortage of independent Kocay-type equations is never the obstruction: the difficulty is precisely whether the deck map is injective, i.e., whether $d(n)=\psi(n)$.

Problem Statement

Let $n\ge3$ be an integer and let $\psi(n)$ denote the number of mutually nonisomorphic simple graphs on $n$ vertices. For a finite family $\mathcal{F}$ of sequences $F=(F_1,\dots,F_m)$ of graphs, each on at most $n-1$ vertices, let $M_{\mathcal{F}}$ be the real matrix whose rows are indexed by the sequences $F\in\mathcal{F}$, whose columns are indexed by the isomorphism classes $H$ of $n$-vertex graphs, and whose $(F,H)$-entry is the covering number $c(F,H)$, the number of ways to cover a representative of $H$ by subgraphs isomorphic to $F_1,\dots,F_m$ whose union is all of $H$.

Question: for every $n\ge3$, does there exist such a family $\mathcal{F}$ with $\operatorname{rank}_{\mathbb{R}}(M_{\mathcal{F}})=\psi(n)$? Equivalently: either (a) for every $n\ge3$ there exists a family whose covering-number matrix has rank $\psi(n)$, or (b) for some $n$ every family has rank strictly less than $\psi(n)$. By the equivalence proved in the primary source, (b) holds exactly when there exist two nonisomorphic $n$-vertex graphs with identical decks, and (a) holds exactly when the graph reconstruction conjecture (Kelly–Ulam) is true, i.e., when every simple graph on at least three vertices is determined up to isomorphism by its deck, equivalently $\psi(n)=d(n)$ for all $n$, where $d(n)$ is the number of distinct decks. The problem is to be answered in this full generality, with no restriction on $n$, on the graph class, or on the form of the family.

References

1. Igor C. Oliveira and Bhalchandra D. Thatte, 'An Algebraic Formulation of the Graph Reconstruction Conjecture', Journal of Graph Theory 81(4):351-363, 2016. DOI: 10.1002/jgt.21880 (https://doi.org/10.1002/jgt.21880); preprint arXiv:1301.4121 (https://arxiv.org/abs/1301.4121).
2. W. L. Kocay, 'Some new methods in reconstruction theory', in Combinatorial Mathematics IX, Lecture Notes in Mathematics, Springer, 1982, pp. 89-114. DOI: 10.1007/bfb0061974 (https://doi.org/10.1007/bfb0061974).
3. P. J. Kelly, 'A congruence theorem for trees', Pacific Journal of Mathematics 7(1):961-968, 1957. DOI: 10.2140/pjm.1957.7.961 (https://doi.org/10.2140/pjm.1957.7.961).
4. S. M. Ulam, 'A Collection of Mathematical Problems', Interscience Tracts in Pure and Applied Mathematics No. 8, Interscience Publishers, New York, 1960. Digitized copy at https://archive.org/details/ACollectionOfMathematicalProblems.
5. John C. Oxtoby, 'Book Review: A Collection of Mathematical Problems', Bulletin of the American Mathematical Society 66(5):361-364, 1960. DOI: 10.1090/S0002-9904-1960-10447-8 (https://doi.org/10.1090/S0002-9904-1960-10447-8).
6. P. K. Stockmeyer, 'The falsity of the reconstruction conjecture for tournaments', Journal of Graph Theory 1(1):19-25, 1977. DOI: 10.1002/jgt.3190010108 (https://doi.org/10.1002/jgt.3190010108).
7. P. K. Stockmeyer, 'A census of non-reconstructable digraphs, I: Six related families', Journal of Combinatorial Theory, Series B 31(2):232-239, 1981. DOI: 10.1016/S0095-8956(81)80027-5 (https://doi.org/10.1016/S0095-8956(81)80027-5).
8. Béla Bollobás, 'Almost every graph has reconstruction number three', Journal of Graph Theory 14(1):1-4, 1990. DOI: 10.1002/jgt.3190140102 (https://doi.org/10.1002/jgt.3190140102).
9. Brendan D. McKay, 'Reconstruction of small graphs and digraphs', Australasian Journal of Combinatorics 83:448-457, 2022; preprint arXiv:2102.01942 (https://arxiv.org/abs/2102.01942).
10. Irene Heinrich, Masashi Kiyomi, Yota Otachi, Pascal Schweitzer, 'Interval Graphs are Reconstructible', 2025. arXiv:2504.02353 (https://arxiv.org/abs/2504.02353).
11. Joshua Cooper, Krystal Guo, Utku Okur, 'Characteristic Polynomials and Hypergraph Generating Functions via Heaps of Pieces', 2024. arXiv:2411.03567 (https://arxiv.org/abs/2411.03567).
12. Ameneh Farhadian, 'A Simple Explanation for the Reconstruction of Graphs', 2017. arXiv:1704.01454 (https://arxiv.org/abs/1704.01454).
13. Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, Nelly Villamizar, 'Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture', 2026. arXiv:2604.16567 (https://arxiv.org/abs/2604.16567).