simple_graph_has_facial_distinguishing_labeling
A simple graph G on Fin n with decidable adjacency and dart permutation σ admits an adjacent-facial-sum-distinguishing proper vertex labeling with bound k if there exists a coloring c : Fin n → Fin (k + 1) such that c u ≠ c v whenever G.Adj u v, and for every dart d of G, simple_graph_face_sum G σ (fun v => (c v : ℕ)) d ≠ simple_graph_face_sum G σ (fun v => (c v : ℕ)) d.symm.
Statement
def simple_graph_has_facial_distinguishing_labeling {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) (k : ℕ) : Prop
- Defined in
- arXiv:2611.18384 Def. 2.1
- Verified
- 16 Nov 2026
- Axioms
- none listed
- Built on 1
- simple_graph_face_sumGiven a simple graph G on Fin n with decidable adjacency, a permutation σ of G.Dart, a vertex weighting c : Fin n → ℕ, and a dart d :…
- Used by 1
- facial_distinguishing_labeling_monotoneFor any simple graph G on Fin n with decidable adjacency, dart permutation σ, and natural numbers k ≤ k', if G admits an…
Read back from the Lean
The predicate simple_graph_has_facial_distinguishing_labeling asserts that for a simple graph G on vertices Fin n, a dart permutation σ : Equiv.Perm G.Dart, and a natural number k, there exists a vertex labeling c : Fin n → Fin (k + 1) such that: 1. c is a proper vertex coloring: for every pair of vertices u, v : Fin n, if G.Adj u v, then c u ≠ c v. 2. c distinguishes adjacent faces: for every dart d : G.Dart, the face sum of d is not equal to the face sum of d.symm, where the face sum of a dart is the sum of (c v : ℕ) over all distinct vertices v that appear as the source vertex d'.fst of some dart d' in the cycle of d under the permutation d' ↦ σ (d'.symm).
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
/-- Predicate that G admits an adjacent-facial-sum-distinguishing proper vertex labeling with labels in {0, ..., k}. -/ def simple_graph_has_facial_distinguishing_labeling {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) (k : ℕ) : Prop := ∃ c : Fin n → Fin (k + 1), (∀ u v, G.Adj u v → c u ≠ c v) ∧ ∀ d : G.Dart, simple_graph_face_sum G σ (fun v => (c v : ℕ)) d ≠ simple_graph_face_sum G σ (fun v => (c v : ℕ)) d.symm