AFTD Auto-Formalizing Theoretical Domains

is_strong_odd_coloring

def

A vertex coloring f : V → κ of a finite simple graph G is a strong odd coloring if it is proper and, for every vertex v and every color c, the number of neighbors of v colored c is either zero or odd.

Statement

def is_strong_odd_coloring {V κ : Type*} [Fintype V] [DecidableEq κ]
    (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → κ) : Prop
Defined in
arXiv:2610.34874
Verified
27 Oct 2026
Axioms
none listed
Used by 3

Read back from the Lean

For a finite type V, a type κ with decidable equality, a simple graph G on V with decidable adjacency, and a vertex-coloring function f : V → κ, is_strong_odd_coloring G f asserts that: 1. f is a proper coloring: for all vertices u, v : V, if u and v are adjacent in G, then f u ≠ f v; and 2. For every vertex v : V and every color c : κ, the set of neighbors of v assigned color c is either empty or has odd cardinality (i.e., every color appearing in the neighborhood of v appears an odd number of times).

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 proper coloring where each color appearing on the neighborhood of any vertex appears an odd number of times. -/
def is_strong_odd_coloring {V κ : Type*} [Fintype V] [DecidableEq κ]
    (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → κ) : Prop := (∀ {u v : V}, G.Adj u v → f u ≠ f v) ∧
  ∀ (v : V) (c : κ),
    (G.neighborFinset v).filter (fun u => f u = c) = ∅ ∨
    Odd ((G.neighborFinset v).filter (fun u => f u = c)).card
See it in the graphDiscuss this resultChallenge it