SignedGraph
structure
A signed graph on vertex type V consists of an underlying simple graph and a signature assigning to each edge a value in {1, -1}.
Statement
structure SignedGraph (V : Type*)
- Defined in
- arXiv:2611.13901, Sec. 2.1
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Used by 15
- 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…
- SignedGraph.IsNetRegularA signed graph G on a finite vertex set V is net-regular if there exists an integer d such that every vertex v of G has net-degree equal…
- SignedGraph.netDegreeThe net-degree of a vertex v in a finite signed graph G is the sum over all vertices w of the extended edge sign between v and w.
- SignedGraph.switchThe switching of a signed graph G at a vertex v is the signed graph with the same underlying graph where the sign of every edge incident…
- SignedGraph.IsBalancedPartitionA pair of disjoint finsets A and B partitioning the vertex set Finset.univ of a signed graph G is a balance partition if every edge whose…
- SignedGraph.edgeSignThe extended edge sign between two vertices u and v in a signed graph G is the signature of the edge if u and v are adjacent, and 0…
- 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…
- signed_graph_balanced_partition_unique_connectedAny two balance partitions of the same connected signed graph agree up to exchanging their two parts.
- 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…
- 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…
- 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…
- SignedGraph.IsReconstructibleA signed graph G on a finite type V with decidable equality is reconstructible from its switching deck if every signed graph G' on a…
- signed_graph_isNetRegular_of_netDegree_eqIf every vertex v of a finite signed graph G has net-degree equal to a constant integer d, then G is net-regular.
- 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…
- SignedGraph.IsSwitchPartnerA vertex w distinct from v is a switch partner of v in G if switching G at v and then at w is not isomorphic to G but has the same…
Read back from the Lean
A SignedGraph on a type of vertices V consists of:
1. graph: a simple graph on vertex type V (SimpleGraph V),
2. sgn: an edge-labeling function assigning an integer (Int) to each edge e in the edge set of graph (graph.edgeSet),
3. sgn_mem: a condition requiring that for every edge e : graph.edgeSet, sgn e = 1 or sgn e = -1.
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 consists of a simple graph and an edge signature with values in {-1, 1}. -/ structure SignedGraph (V : Type*) where graph : SimpleGraph V sgn : graph.edgeSet → Int sgn_mem : ∀ e, sgn e = 1 ∨ sgn e = -1