/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

The reconstruction conjecture

References:

    Wikipedia

    [Ke57] Kelly, P. J. (1957). "A congruence theorem for trees." Pacific J. Math. 7, pp. 961--968.

    [Ul60] Ulam, S. M. (1960). A Collection of Mathematical Problems. Interscience, New York.

    [Ha64] Harary, F. (1964). "On the reconstruction of a graph from a collection of subgraphs." In Theory of Graphs and its Applications, Academia, Prague, pp. 47--52.

    [Lo72] Lovász, L. (1972). "A note on the line reconstruction problem." J. Combin. Theory Ser. B 13, pp. 309--310.

    [Mu77] Müller, V. (1977). "The edge reconstruction hypothesis is true for graphs with more than n·log n edges." J. Combin. Theory Ser. B 22, pp. 281--283.

    [Bo91] Bondy, J. A. (1991). "A graph reconstructor's manual." In Surveys in Combinatorics, LMS Lecture Note Series 166, Cambridge University Press, pp. 221--252.

@[expose] public sectionnamespace ReconstructionConjecturevariable {V W : Type*}

Two graphs are hypomorphic if there is a bijection σ between their vertex sets such that the vertex-deleted subgraphs G - v and H - σ v are isomorphic for every vertex v; i.e. G and H have the same deck of vertex-deleted subgraphs.

def Hypomorphic (G : SimpleGraph V) (H : SimpleGraph W) : Prop := ∃ σ : V ≃ W, ∀ v : V, Nonempty (G.induce {v}ᶜ ≃g H.induce {σ v}ᶜ)

Two graphs are edge-hypomorphic if there is a bijection σ between their edge sets such that the edge-deleted subgraphs G - e and H - σ e are isomorphic for every edge e; i.e. G and H have the same deck of edge-deleted subgraphs.

def EdgeHypomorphic (G : SimpleGraph V) (H : SimpleGraph W) : Prop := ∃ σ : G.edgeSet ≃ H.edgeSet, ∀ e : G.edgeSet, Nonempty (G.deleteEdges {(e : Sym2 V)} ≃g H.deleteEdges {((σ e : H.edgeSet) : Sym2 W)})

Isomorphic graphs are hypomorphic: an isomorphism restricts to an isomorphism between corresponding vertex-deleted subgraphs.

@[category API, AMS 5] lemma Hypomorphic.of_iso {G : SimpleGraph V} {H : SimpleGraph W} (f : G ≃g H) : Hypomorphic G H := V:Type u_1W:Type u_2G:SimpleGraph VH:SimpleGraph Wf:G ≃g H⊢ Hypomorphic G H V:Type u_1W:Type u_2G:SimpleGraph VH:SimpleGraph Wf:G ≃g Hv:Vx:V⊢ x ∈ {v}ᶜ ↔ f.toEquiv x ∈ {f.toEquiv v}ᶜV:Type u_1W:Type u_2G:SimpleGraph VH:SimpleGraph Wf:G ≃g Hv:V⊢ ∀ {a b : ↑{v}ᶜ}, (SimpleGraph.induce {f.toEquiv v}ᶜ H).Adj ((f.subtypeEquiv ⋯) a) ((f.subtypeEquiv ⋯) b) ↔ (SimpleGraph.induce {v}ᶜ G).Adj a b V:Type u_1W:Type u_2G:SimpleGraph VH:SimpleGraph Wf:G ≃g Hv:Vx:V⊢ x ∈ {v}ᶜ ↔ f.toEquiv x ∈ {f.toEquiv v}ᶜ All goals completed! 🐙 V:Type u_1W:Type u_2G:SimpleGraph VH:SimpleGraph Wf:G ≃g Hv:V⊢ ∀ {a b : ↑{v}ᶜ}, (SimpleGraph.induce {f.toEquiv v}ᶜ H).Adj ((f.subtypeEquiv ⋯) a) ((f.subtypeEquiv ⋯) b) ↔ (SimpleGraph.induce {v}ᶜ G).Adj a b V:Type u_1W:Type u_2G:SimpleGraph VH:SimpleGraph Wf:G ≃g Hv:Va:↑{v}ᶜb:↑{v}ᶜ⊢ (SimpleGraph.induce {f.toEquiv v}ᶜ H).Adj ((f.subtypeEquiv ⋯) a) ((f.subtypeEquiv ⋯) b) ↔ (SimpleGraph.induce {v}ᶜ G).Adj a b All goals completed! 🐙

Hypomorphic graphs have the same number of vertices.

@[category API, AMS 5] lemma Hypomorphic.card_eq [Fintype V] [Fintype W] {G : SimpleGraph V} {H : SimpleGraph W} (h : Hypomorphic G H) : Fintype.card V = Fintype.card W := V:Type u_1W:Type u_2inst✝¹:Fintype Vinst✝:Fintype WG:SimpleGraph VH:SimpleGraph Wh:Hypomorphic G H⊢ Fintype.card V = Fintype.card W V:Type u_1W:Type u_2inst✝¹:Fintype Vinst✝:Fintype WG:SimpleGraph VH:SimpleGraph Wσ:V ≃ W⊢ Fintype.card V = Fintype.card W All goals completed! 🐙

Any two graphs on subsingleton vertex types are isomorphic.

@[category API, AMS 5] lemma nonempty_iso_of_subsingleton [Subsingleton V] [Subsingleton W] (G : SimpleGraph V) (H : SimpleGraph W) (e : V ≃ W) : Nonempty (G ≃g H) := V:Type u_1W:Type u_2inst✝¹:Subsingleton Vinst✝:Subsingleton WG:SimpleGraph VH:SimpleGraph We:V ≃ W⊢ Nonempty (G ≃g H) V:Type u_1W:Type u_2inst✝¹:Subsingleton Vinst✝:Subsingleton WG:SimpleGraph VH:SimpleGraph We:V ≃ W⊢ ∀ {a b : V}, H.Adj (e a) (e b) ↔ G.Adj a b V:Type u_1W:Type u_2inst✝¹:Subsingleton Vinst✝:Subsingleton WG:SimpleGraph VH:SimpleGraph We:V ≃ Wa:Vb:V⊢ H.Adj (e a) (e b) ↔ G.Adj a b V:Type u_1W:Type u_2inst✝¹:Subsingleton Vinst✝:Subsingleton WG:SimpleGraph VH:SimpleGraph We:V ≃ Wa:V⊢ H.Adj (e a) (e a) ↔ G.Adj a a All goals completed! 🐙

The reconstruction conjecture (Kelly [Ke57], Ulam [Ul60]).

Every finite simple graph on at least three vertices is determined up to isomorphism by its deck of vertex-deleted subgraphs: any two hypomorphic graphs on at least three vertices are isomorphic.

@[category research open, AMS 5] theorem reconstruction_conjecture {V W : Type} [Fintype V] [Fintype W] (hV : 3 ≤ Fintype.card V) (G : SimpleGraph V) (H : SimpleGraph W) (h : Hypomorphic G H) : Nonempty (G ≃g H) := V:TypeW:Typeinst✝¹:Fintype Vinst✝:Fintype WhV:3 ≤ Fintype.card VG:SimpleGraph VH:SimpleGraph Wh:Hypomorphic G H⊢ Nonempty (G ≃g H) All goals completed! 🐙

Trees are reconstructible (Kelly [Ke57]).

Every tree on at least three vertices is determined up to isomorphism by its deck of vertex-deleted subgraphs.

@[category research solved, AMS 5] theorem reconstruction_conjecture.variants.tree {V W : Type} [Fintype V] [Fintype W] (hV : 3 ≤ Fintype.card V) (G : SimpleGraph V) (H : SimpleGraph W) (hc : G.Connected) (ha : G.IsAcyclic) (h : Hypomorphic G H) : Nonempty (G ≃g H) := V:TypeW:Typeinst✝¹:Fintype Vinst✝:Fintype WhV:3 ≤ Fintype.card VG:SimpleGraph VH:SimpleGraph Whc:G.Connectedha:G.IsAcyclich:Hypomorphic G H⊢ Nonempty (G ≃g H) All goals completed! 🐙

Disconnected graphs are reconstructible.

Every disconnected graph on at least three vertices is determined up to isomorphism by its deck of vertex-deleted subgraphs; see [Bo91].

@[category research solved, AMS 5] theorem reconstruction_conjecture.variants.disconnected {V W : Type} [Fintype V] [Fintype W] (hV : 3 ≤ Fintype.card V) (G : SimpleGraph V) (H : SimpleGraph W) (hd : ¬G.Connected) (h : Hypomorphic G H) : Nonempty (G ≃g H) := V:TypeW:Typeinst✝¹:Fintype Vinst✝:Fintype WhV:3 ≤ Fintype.card VG:SimpleGraph VH:SimpleGraph Whd:¬G.Connectedh:Hypomorphic G H⊢ Nonempty (G ≃g H) All goals completed! 🐙

The hypothesis of three vertices is necessary.

The two graphs on two vertices — the single edge and its complement — are hypomorphic (both decks consist of two one-vertex graphs) but not isomorphic.

hss:∀ (v : Fin 2), Subsingleton ↑{v}ᶜ⊢ Hypomorphic ⊤ ⊥ hss:∀ (v : Fin 2), Subsingleton ↑{v}ᶜv:Fin 2⊢ Nonempty (SimpleGraph.induce {v}ᶜ ⊤ ≃g SimpleGraph.induce {(Equiv.refl (Fin 2)) v}ᶜ ⊥) hss:∀ (v : Fin 2), Subsingleton ↑{v}ᶜv:Fin 2this:Subsingleton ↑{v}ᶜ⊢ Nonempty (SimpleGraph.induce {v}ᶜ ⊤ ≃g SimpleGraph.induce {(Equiv.refl (Fin 2)) v}ᶜ ⊥) All goals completed! 🐙 ⊢ IsEmpty (⊤ ≃g ⊥) All goals completed! 🐙

The edge reconstruction conjecture (Harary [Ha64]).

Every finite simple graph with at least four edges is determined up to isomorphism by its deck of edge-deleted subgraphs: any two edge-hypomorphic graphs on the same vertex set with at least four edges are isomorphic.

@[category research open, AMS 5] theorem edge_reconstruction_conjecture {V : Type} [Fintype V] (G H : SimpleGraph V) (hE : 4 ≤ G.edgeSet.ncard) (h : EdgeHypomorphic G H) : Nonempty (G ≃g H) := V:Typeinst✝:Fintype VG:SimpleGraph VH:SimpleGraph VhE:4 ≤ G.edgeSet.ncardh:EdgeHypomorphic G H⊢ Nonempty (G ≃g H) All goals completed! 🐙

Lovász (1972): graphs with more than half of all possible edges are edge-reconstructible.

If a graph on n vertices has more than n (n - 1) / 4 edges, then it is determined up to isomorphism by its deck of edge-deleted subgraphs.

Reference: [Lo72].

@[category research solved, AMS 5] theorem edge_reconstruction_conjecture.variants.lovasz {V : Type} [Fintype V] (G H : SimpleGraph V) (hE : (Fintype.card V).choose 2 < 2 * G.edgeSet.ncard) (h : EdgeHypomorphic G H) : Nonempty (G ≃g H) := V:Typeinst✝:Fintype VG:SimpleGraph VH:SimpleGraph VhE:(Fintype.card V).choose 2 < 2 * G.edgeSet.ncardh:EdgeHypomorphic G H⊢ Nonempty (G ≃g H) All goals completed! 🐙

Müller (1977): graphs with many edges are edge-reconstructible.

If a graph on n vertices with m edges satisfies n! < 2 ^ (m - 1), then it is determined up to isomorphism by its deck of edge-deleted subgraphs.

Reference: [Mu77].

@[category research solved, AMS 5] theorem edge_reconstruction_conjecture.variants.mueller {V : Type} [Fintype V] (G H : SimpleGraph V) (hE : Nat.factorial (Fintype.card V) < 2 ^ (G.edgeSet.ncard - 1)) (h : EdgeHypomorphic G H) : Nonempty (G ≃g H) := V:Typeinst✝:Fintype VG:SimpleGraph VH:SimpleGraph VhE:(Fintype.card V).factorial < 2 ^ (G.edgeSet.ncard - 1)h:EdgeHypomorphic G H⊢ Nonempty (G ≃g H) All goals completed! 🐙end ReconstructionConjecture