AFTD Auto-Formalizing Theoretical Domains

SignedGraph.IsReconstructible

def

A signed graph G on a finite type V with decidable equality is reconstructible from its switching deck if every signed graph G' on a finite type V' with decidable equality that has the same switching deck as G is isomorphic to G.

Statement

def SignedGraph.IsReconstructible {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) : Prop
Defined in
arXiv:2611.13901, Sec. 2.2
Verified
11 Nov 2026
Axioms
none listed
Built on 3
  • SignedGraphA signed graph on vertex type V consists of an underlying simple graph and a signature assigning to each edge a value in {1, -1}.
  • SignedGraph.IsIsomorphicTwo signed graphs G1 and G2 are isomorphic if there is an isomorphism f between their underlying simple graphs that preserves the signs of…
  • SignedGraph.SameDeckTwo signed graphs G1 and G2 on finite types V1 and V2 with decidable equality have the same switching deck if there exists an equivalence…
Used by 4

Read back from the Lean

Given a type V with decidable equality and finite cardinality, and a signed graph G on V, SignedGraph.IsReconstructible G asserts that for every type V' with decidable equality and finite cardinality, and for every signed graph G' on V', if G and G' have the same deck (SignedGraph.SameDeck G G'), then G and G' are isomorphic (SignedGraph.IsIsomorphic G G').

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A signed graph is reconstructible if every signed graph with the same switching deck is isomorphic to it. -/
def SignedGraph.IsReconstructible {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) : Prop :=
  ∀ {V' : Type*} [DecidableEq V'] [Fintype V'] (G' : SignedGraph V'),
    SignedGraph.SameDeck G G' → SignedGraph.IsIsomorphic G G'
See it in the graphDiscuss this resultChallenge it