Papex

Open problem · Mathematics · Open

Reconstruction conjecture

Is every graph with at least three vertices determined by its collection of subgraphs with one vertex removed?

Summary

Due to Kelly and Ulam, the conjecture says that the “deck” of vertex-deleted subgraphs fixes a graph up to isomorphism. It is proved for several classes, including trees and regular graphs, but open in general.

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

  1. 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.
  2. 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]?
  3. 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]?
  4. 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]?
  5. 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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. McKay, B. D. (2022). Reconstruction of small graphs and digraphs. Australasian Journal of Combinatorics 83(3), 448–457. Source · Checked 16 Oct 2026
  9. 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
  10. 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
  11. 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
  12. Wikipedia. List of unsolved problems in mathematics (revision of 15 October 2026). Source · Checked 16 Oct 2026

Page reviewed 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.

More in Mathematics