AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_facial_distinguishing_labeling

def

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

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
See it in the graphDiscuss this resultChallenge it