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
- signed_graph_reconstructible_balanced_mono_pair_fixedLet G be a connected balanced signed graph on at least seven vertices, with a specified balance partition. Suppose distinct vertices a and…
- signed_graph_reconstructible_balanced_mono_invariantA connected balanced signed graph is reconstructible from its switching deck if its underlying graph has an automorphism-invariant vertex…
- signed_graph_reconstructible_balanced_three_fixedEvery connected balanced signed graph on at least seven vertices is reconstructible from its switching deck if its underlying graph has…
- signed_graph_reconstructible_balanced_mixed_twin_pairLet G be a connected balanced signed graph on at least five vertices, with a specified balance partition. Suppose distinct vertices a and…
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'