Reconstruction conjecture
Is every graph with at least three vertices determined by its collection of subgraphs with one vertex removed?
Summary
Why it is open
A graph is a set of vertices, some pairs of which are joined by edges. Deleting one vertex and its edges gives a card, and the multiset of all cards of a graph, each known only up to isomorphism (that is, with the names of the vertices hidden), is its deck [7]. A graph is reconstructible if no other graph has the same deck, and the reconstruction conjecture asserts that every graph with at least three vertices is reconstructible; the restriction is needed because the two graphs on two vertices have the same deck [7]. Alexandr Kostochka and Douglas West attribute the conjecture to Kelly, who first posed it in his thesis of 1942, and to Ulam [7].
A resolution would be a proof for all finite graphs, or two non-isomorphic graphs with the same deck. Many families of graphs are known to be reconstructible, but Kostochka and West write that the conjecture "remains wide open" [7]. No prize body sets conditions; the status on this page follows Wikipedia's list of unsolved problems in mathematics [12].
The name covers several related questions. Frank Harary's set reconstruction conjecture is a stronger version that uses only the reduced deck, which records which cards occur but not how often, for graphs with at least four vertices [8]. The edge reconstruction conjecture, posed by Harary in 1964, asks whether a graph with at least four edges is determined by its edge deck, the cards obtained by deleting one edge at a time [10]. Kelly also conjectured that for each ℓ, all large enough graphs are determined by the subgraphs left after deleting ℓ vertices [7]. The direct analogues for directed graphs, hypergraphs and infinite graphs are false [2, 5, 10].
What is known
Classes of graphs (1957–2025). Kelly proved in 1957 that trees (connected graphs without cycles) with at least three vertices are reconstructible [1, 5]. His argument starts from two lemmas: the deck fixes how many times each smaller graph occurs as a subgraph, and the degree (number of neighbours) of each deleted vertex [1]. Families now known to be reconstructible include disconnected graphs, trees and regular graphs, in which all vertices have the same degree [7]. In 1988 Yang Yongzhi showed that the conjecture is true for all finite graphs if it is true for the 2-connected ones, which stay connected when any one vertex is removed [3]. For Kelly's version with ℓ deleted vertices, Kostochka, Mina Nahvi, West and Dara Zirlin proved that every tree with at least 6ℓ + 11 vertices is determined by its subgraphs with ℓ vertices deleted [11].
How many cards are needed (1990–2021). The reconstruction number of a graph, defined by Harary and M. Plantholt, is the least number of its cards that determine it [7]. Béla Bollobás proved their conjecture that almost every graph has reconstruction number three [4]. W. J. Myrvold showed the same for trees with at least five vertices, and no graph has reconstruction number two, because two cards cannot show whether the two deleted vertices were adjacent [7]. On the other side, Andrew Bowler, Paul Brown and Trevor Fenner found infinite families of pairs of graphs that share 2⌊(n − 1)/3⌋ cards [7]. Some properties need fewer cards: Carla Groenland, Hannah Guggiari and Alex Scott showed that for large n the number of edges can be computed from any deck missing at most √n/20 cards [6].
Computer searches (1977–2022). Brendan McKay checked all graphs with 9 vertices in 1977 and all graphs with 11 vertices in 1997 [8]. In 2022 he reported that all graphs with 4 to 13 vertices are reconstructible, even from their reduced decks; there are 50,502,031,367,952 graphs on 13 vertices, and the testing of more than 6 × 10^13 graphs took about 1.5 years on Intel processors [8]. The same search covers larger graphs in restricted classes, among them triangle-free graphs (no three mutually adjacent vertices) up to 16 vertices and graphs with maximum degree at most 3 up to 22 [8].
Where the analogue fails. In a tournament, every pair of vertices is joined by exactly one arrow. Paul Stockmeyer showed in 1977 that the corresponding conjecture is false for tournaments, with counterexamples of every order 2^t + 1 and 2^t + 2 [2, 8]; he later extended the construction to all orders 2^s + 2^t with t > s ≥ 0, including directed graphs that are not tournaments [8]. McKay's searches of all tournaments up to 13 vertices and all directed graphs up to 8 vertices found no examples beyond those already known [8]. The conjecture also fails for hypergraphs, in which an edge may contain more than two vertices [10]. For infinite graphs, Nathan Bowler, Joshua Erde, Peter Heinig, Florian Lehner and Max Pitz constructed two non-isomorphic infinite trees of maximum degree three whose cards match one for one, a counterexample to the 1972 Harary–Schwenk–Scott conjecture that every locally finite tree is reconstructible [5].
Edge reconstruction. If a graph with at least four edges and no isolated vertices is reconstructible from its vertex deck, it is also reconstructible from its edge deck [10]; D. Stolee checked the edge conjecture up to 12 vertices [8]. By Whitney's isomorphism theorem, the edge conjecture is equivalent to the vertex reconstructibility of all line graphs, in which the vertices stand for the edges of another graph [10]. Graphs without an induced claw, a vertex with three mutually non-adjacent neighbours, were shown in 1988 to be edge-reconstructible [10].
Recent claims. In a 2024 article in Information Sciences, Robert John O'Shea and Louis Wilkins introduced a "vertex-substitution framework", in which each card receives a substitute vertex joined to all others by edges of a distinctive weight, and wrote that "the Kelly-Ulam reconstruction conjecture is verified for finite, undirected graphs on at least three vertices" [9]. A corrigendum followed in July 2024 [9]. No published response to the argument was found when this page was checked on 16 October 2026, and Wikipedia's list still included the conjecture as unsolved [12].
Main approaches
Structure from the deck. Show that the deck determines enough structure to rebuild every graph in a class, starting from subgraph counts and degrees [1, 7]. Strongest evidence: trees, disconnected graphs and regular graphs are settled [7], and Yang's reduction means that 2-connected graphs would suffice [3]. Main difficulty: despite these classes, the conjecture "remains wide open", Kostochka and West write [7].
Exhaustive computation. McKay builds every graph by adding a vertex to a smaller one, in a way that guarantees that two graphs with the same reduced deck arise from the same parents, so decks need only be compared in small batches [8]. Strongest evidence: every graph with up to 13 vertices, and larger graphs in restricted classes [8]. Main difficulty: the number of graphs grows quickly, from 1,018,997,864 on 11 vertices to 50,502,031,367,952 on 13 [8].
Fewer cards and stronger statements. Ask how few cards determine a graph, or a property such as the number of edges, or what remains determined when more vertices are deleted [6, 7]. Strongest evidence: almost every graph is determined by three of its cards [4], and the number of edges by all but √n/20 cards for large n [6]. Main difficulty: some pairs of graphs share 2⌊(n − 1)/3⌋ cards, and for ℓ deleted vertices, V. Nýdl showed that the number of vertices needed grows faster than linearly in ℓ [7].
Algebraic reformulation. Restate the conjecture in a language with other tools [10]. Strongest evidence: Maxine Calle and Julian Gould showed that, for each n, the edge reconstruction conjecture for graphs with n edges is equivalent to the injectivity of a map into a group defined by combinatorial K-theory, and used the framework to disprove a stronger, generalised version [10]. Main difficulty: the reformulation does not decide the conjecture; the authors "do not prove (or disprove) any part of this conjecture" [10].
Open sub-questions
- Fourteen vertices. McKay's search uses a hash of edge and triangle counts in the cards and an invariant built from the cards' degree sequences, and runs full isomorphism checks only on graphs these do not separate; 13 vertices took about 1.5 years [8]. Which cheaper card invariant would cut the isomorphism checks enough to make all graphs on 14 vertices feasible? See the Papex page on the graph isomorphism problem.
- Tournaments beyond 13 vertices. Is every non-reconstructible tournament on 14 or more vertices one of Stockmeyer's, as for tournaments with 9 to 13 vertices [2, 8]?
- Edges from fewer cards. Can the number of missing cards that still allows the number of edges to be computed grow linearly in n, beyond the √n/20 of Groenland and colleagues [6]?
- Reconstruction numbers. Is the reconstruction number of every n-vertex graph at most n/2 + 2, with equality only in the cases Harary and Plantholt listed [7]?
- Trees with ℓ vertices deleted. Nýdl conjectured that trees with at least 2ℓ + 1 vertices are determined after deleting ℓ vertices [7]. For ℓ = 3, are the trees with 7 to 28 vertices, below the 6ℓ + 11 bound [11], all determined?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Kelly, P. J. (1957). A congruence theorem for trees. Pacific Journal of Mathematics 7(1), 961–968. 10.2140/pjm.1957.7.961 · Checked 16 Oct 2026
- Stockmeyer, P. K. (1977). The falsity of the reconstruction conjecture for tournaments. Journal of Graph Theory 1(1), 19–25. 10.1002/jgt.3190010108 · Checked 16 Oct 2026
- Yang, Y. (1988). The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of Graph Theory 12(2), 237–243. 10.1002/jgt.3190120214 · Checked 16 Oct 2026
- Bollobás, B. (1990). Almost every graph has reconstruction number three. Journal of Graph Theory 14(1), 1–4. 10.1002/jgt.3190140102 · Checked 16 Oct 2026
- Bowler, N., Erde, J., Heinig, P., Lehner, F. & Pitz, M. (2017). A counterexample to the reconstruction conjecture for locally finite trees. Bulletin of the London Mathematical Society 49(4), 630–648. 10.1112/blms.12053 · Checked 16 Oct 2026
- Groenland, C., Guggiari, H. & Scott, A. (2021). Size reconstructibility of graphs. Journal of Graph Theory 96(2), 326–337 (published online 2020). 10.1002/jgt.22616 · Checked 16 Oct 2026
- Kostochka, A. V. & West, D. B. (2021). On reconstruction of graphs from the multiset of subgraphs obtained by deleting ℓ vertices. IEEE Transactions on Information Theory 67(6), 3278–3286. 10.1109/tit.2020.2983678 · Checked 16 Oct 2026
- McKay, B. D. (2022). Reconstruction of small graphs and digraphs. Australasian Journal of Combinatorics 83(3), 448–457. Source · Checked 16 Oct 2026
- O'Shea, R. J. & Wilkins, L. (2024). Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs. Information Sciences 654, 119858 (published online 2023); corrigendum in 675, 120738 (2024), DOI 10.1016/j.ins.2024.120738. 10.1016/j.ins.2023.119858 · Checked 16 Oct 2026
- Calle, M. E. & Gould, J. J. (2025). A combinatorial K-theory perspective on the edge reconstruction conjecture in graph theory. Homology, Homotopy and Applications 27(1), 293–322. 10.4310/HHA.2025.v27.n1.a16 · Checked 16 Oct 2026
- Kostochka, A. V., Nahvi, M., West, D. B. & Zirlin, D. (2025). Trees with at least 6ℓ + 11 vertices are ℓ-reconstructible. Graphs and Combinatorics 41(6), 133. 10.1007/s00373-025-02968-9 · Checked 16 Oct 2026
- Wikipedia. List of unsolved problems in mathematics (revision of 15 October 2026). Source · Checked 16 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.