MathDB

Harary's Edge Reconstruction Conjecture for graphs

At least 15 years old · documented by

Let GG be a graph. An edge-deck is the multiset

ED(G)=G−e:e∈E(G).\mathcal{E}\mathcal{D}(G)=\\{G-e:e\in E(G)\\}.

A graph is edge-reconstructible if it is uniquely determined, up to isomorphism, by its edge-deck. Harary's Edge Reconstruction Conjecture. Every graph with at least 44 edges is edge-reconstructible, i.e., it is uniquely determined by its edge-deck. This edge-focused variant of graph reconstruction was proposed by Harary and remains open in general.

References

Primary source

Alexander Clifton, Xiaonan Liu, Reem Mahmoud and Abhinav Shantanam, “Reconstruction and Edge Reconstruction of Triangle-free Graphs”, arXiv:2210.00338 (2022).

Additional references

2 papers in this index state this conjecture (2010–2022). The statement above is taken from the most recent of them; the others are arXiv:1004.2375.

graph-reconstructiongraph-theory
Posted

Progress summary

Refreshed
Claimed progress

The conjecture remains open, with progress only for restricted families of graphs and no general proof or counterexample found.

Harary proposed in 1964 that every graph with at least four edges is uniquely determined by the multiset of graphs obtained by deleting one edge at a time. The general assertion remains unresolved.

Known results

  • Müller established edge reconstruction when the average degree satisfies d‾≥2log⁡2∣V∣\overline d \ge 2\log_2 |V|.
  • Greenwell showed that, for graphs with at least four edges and no isolated vertices, the vertex-deck is determined by the edge-deck.
  • A 2022 paper proved edge reconstructibility for two classes, G2\mathcal{G}_2 and G3\mathcal{G}_3, of triangle-free graphs.
  • A 2024 paper proved the conjecture for unicyclic graphs having at least three non-isomorphic subtrees.

2024 structural reformulation and limitation

A 2024 paper reformulated the conjecture as injectivity of a map into K0(Γn,n−1)K_0(\Gamma_{n,n-1}) and explicitly did not prove or disprove it. It did disprove a stronger statement about reconstructing collections from unions of edge-decks, which does not refute the ordinary conjecture.

Current status (as of August 2026): The general conjecture is open; restricted graph classes are settled, but no general proof or counterexample is recorded here.

Sources

Solutions 0

No solutions have been posted yet.