AFTD Auto-Formalizing Theoretical Domains

strong_odd_coloring_insert_vertex

theoremverified

Let g be a colouring of a finite simple graph G which is a strong odd colouring of G - v; if g v avoids the colours of all neighbours of v and also the colours of all their other neighbours, and every colour appears 0 or an odd number of times among the neighbours of v, then g is a strong odd colouring of G.

Statement

theorem strong_odd_coloring_insert_vertex {V κ : Type} [Fintype V] [DecidableEq V]
    [DecidableEq κ] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (g : V → κ)
    (hout : is_strong_odd_coloring (G.induce {x | x ≠ v}) (fun x => g x.1))
    (hproper : ∀ u ∈ G.neighborFinset v, g v ≠ g u)
    (hfar : ∀ u ∈ G.neighborFinset v, ∀ w ∈ G.neighborFinset u, w ≠ v → g v ≠ g w)
    (hpar : ∀ c : κ, {u ∈ G.neighborFinset v | g u = c} = ∅ ∨
      Odd {u ∈ G.neighborFinset v | g u = c}.card) :
    is_strong_odd_coloring G g
Source
step towards sparse_strong_odd_five_list_coloring
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_strong_odd_coloringA 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 proof, explained

The theorem establishes that a strong odd colouring of the induced subgraph G - v extends to G when the colour assigned to v avoids the colours in its neighbourhood and second-order neighbourhood, and the neighbourhood N(v) itself satisfies the odd condition. Properness of the colouring on G holds because edges not incident to v are properly coloured by induction, while edges incident to v avoid g(v) by assumption. For any other vertex x and colour c, if v is not a c-coloured neighbour of x, the monochromatic neighbourhood naturally identifies with that in G - v, preserving emptiness and odd parity. Finally, if x is adjacent to v and g(v) = c, the distance-2 avoidance hypothesis ensures that v is the unique neighbour of x coloured c, giving a neighbourhood of size 1, which is odd.

  1. The problem reduces to verifying properness of the colouring g on G and the odd neighbourhood condition for every vertex and colour in G.

    We unpack the hypothesis that g is a strong odd colouring of the induced subgraph G - v into two components: properness on G - v (hprop') and the odd-or-empty condition on G - v (hpar'). We then split the goal of showing g is a strong odd colouring of G into the corresponding two goals: showing g is proper on all edges of G, and showing that for every vertex and colour in G, the monochromatic neighbourhood is empty or of odd cardinality.

    lines 10–11

      obtain ⟨hprop', hpar'⟩ := hout
      refine ⟨?_, ?_⟩
  2. The colouring g is a proper colouring of G.

    For any edge between vertices a and b in G, we consider whether either endpoint is v. If a = v, then b is in the neighbourhood of v, and by hypothesis hproper, g(v) ≠ g(b). Symmetrically, if b = v, g(a) ≠ g(v) by hproper. If neither endpoint is v, the edge belongs to the induced subgraph G - v, where g is already known to be proper by hprop'.

    lines 12–19

    uses SimpleGraph.mem_neighborFinset

      · intro a b hab
        by_cases ha : a = v
        · subst ha
          exact hproper b ((SimpleGraph.mem_neighborFinset _ _ _).mpr hab)
        by_cases hb : b = v
        · subst hb
          exact (hproper a ((SimpleGraph.mem_neighborFinset _ _ _).mpr hab.symm)).symm
        · exact hprop' (u := ⟨a, ha⟩) (v := ⟨b, hb⟩) hab
  3. The odd neighbourhood condition holds for the vertex v.

    Given an arbitrary vertex x and colour c, we first consider the case x = v. In this case, the condition that the set of neighbours of v coloured c is empty or has odd cardinality is provided directly by the hypothesis hpar c.

    lines 20–23

      · intro x c
        by_cases hx : x = v
        · subst hx
          exact hpar c
  4. When x ≠ v and no neighbour of x coloured c equals v, the set of c-coloured neighbours of x in G is the image of the corresponding set in G - v under the subtype embedding.

    We prove the helper lemma hmap. Under the assumption that every neighbour u of x with g(u) = c satisfies u ≠ v, any such neighbour w belongs to the vertex set of G - v, and the edges of G - v are exactly those of G between vertices other than v. By extensionality and unfolding the definitions of finset filtering and embedding mapping, the monochromatic neighbourhood in G is precisely the image under the canonical subtype embedding of the monochromatic neighbourhood of x in the induced subgraph G - v.

    lines 24–37

    uses Function.Embedding.subtype, Finset.mem_filter, Finset.mem_map, Function.Embedding.coe_subtype, SimpleGraph.mem_neighborFinset

        have hmap : (∀ u, G.Adj x u → g u = c → u ≠ v) →
            (G.neighborFinset x).filter (fun u => g u = c) =
            (((G.induce {y | y ≠ v}).neighborFinset ⟨x, hx⟩).filter
              (fun u => g u.1 = c)).map (Function.Embedding.subtype _) := by
          intro hnv
          ext w
          simp only [Finset.mem_filter, Finset.mem_map, Function.Embedding.coe_subtype]
          constructor
          · rintro ⟨hw, hwc⟩
            have hw' : G.Adj x w := (SimpleGraph.mem_neighborFinset _ _ _).mp hw
            exact ⟨⟨w, hnv w hw' hwc⟩, ⟨(SimpleGraph.mem_neighborFinset _ _ _).mpr hw', hwc⟩, rfl⟩
          · rintro ⟨y, ⟨hy, hyc⟩, rfl⟩
            have hy' : (G.induce {y | y ≠ v}).Adj ⟨x, hx⟩ y := (SimpleGraph.mem_neighborFinset _ _ _).mp hy
            exact ⟨(SimpleGraph.mem_neighborFinset _ _ _).mpr hy', hyc⟩
  5. When x ≠ v and no neighbour of x coloured c equals v, the set of c-coloured neighbours of x in G is empty or has odd cardinality.

    We prove the helper lemma finish. By the inductive hypothesis hpar' on G - v at vertex x, the monochromatic neighbourhood of x with colour c in G - v is either empty or has odd cardinality. In the empty case, its image under an embedding is also empty (Finset.map_eq_empty.mpr). In the odd case, the embedding preserves cardinality (Finset.card_map), so the set in G also has odd cardinality.

    lines 38–48

    uses Finset.map_eq_empty.mpr, Finset.card_map

        have finish : (∀ u, G.Adj x u → g u = c → u ≠ v) →
            ((G.neighborFinset x).filter (fun u => g u = c) = ∅ ∨
              Odd ((G.neighborFinset x).filter (fun u => g u = c)).card) := by
          intro hnv
          rcases hpar' ⟨x, hx⟩ c with h | h
          · left
            rw [hmap hnv]
            exact Finset.map_eq_empty.mpr h
          · right
            rw [hmap hnv, Finset.card_map]
            exact h
  6. If x is adjacent to v and g(v) = c, then the set of neighbours of x coloured c has odd cardinality.

    Suppose x is adjacent to v and g(v) = c. We show that the set of c-coloured neighbours of x is the singleton {v} (hone). Indeed, v is a neighbour of x with g(v) = c. If w is any other neighbour of x with g(w) = c and w ≠ v, then x ∈ N(v) and w ∈ N(x) with w ≠ v; by the distance-2 avoidance hypothesis hfar, g(v) ≠ g(w), contradicting g(v) = c = g(w). Thus the monochromatic neighbourhood equals {v}, which has cardinality 1 (Finset.card_singleton), and 1 is odd (odd_one).

    lines 49–63

    uses Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_singleton, Finset.card_singleton, odd_one

        by_cases hxv : G.Adj x v
        · by_cases hc : g v = c
          · right
            have hone : (G.neighborFinset x).filter (fun u => g u = c) = {v} := by
              ext w
              simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_singleton]
              constructor
              · rintro ⟨hw, hwc⟩
                by_contra hne
                exact hfar x ((SimpleGraph.mem_neighborFinset _ _ _).mpr hxv.symm) w
                  ((SimpleGraph.mem_neighborFinset _ _ _).mpr hw) hne (hc.trans hwc.symm)
              · rintro rfl
                exact ⟨hxv, hc⟩
            rw [hone, Finset.card_singleton]
            exact odd_one
  7. In all remaining cases, the odd neighbourhood condition holds for x and c.

    The two remaining cases are when x is adjacent to v but g(v) ≠ c, and when x is not adjacent to v. In both cases, no neighbour u of x with g(u) = c can equal v: in the first case because g(u) = c ≠ g(v), and in the second because u is adjacent to x while v is not. In each case, this satisfies the antecedent of the helper lemma finish, concluding that the monochromatic neighbourhood is empty or has odd cardinality.

    lines 64–65

          · exact finish fun u _ huc huv => hc (huv ▸ huc)
        · exact finish fun u hu _ huv => hxv (huv ▸ hu)
Finset.mem_singleton
An element b belongs to the singleton {a} if and only if b = a.
Finset.card_singleton
The cardinality of a singleton finset {a} is 1.
odd_one
The natural number 1 is odd.
Finset.mem_filter
An element a belongs to the filter of a finset by a predicate p if and only if a belongs to the original finset and satisfies p.
Finset.mem_map
An element b belongs to the image of a finset under an embedding f if and only if b = f(a) for some element a in the original finset.
Function.Embedding.subtype
The canonical embedding of a subtype into its ambient type.
Function.Embedding.coe_subtype
The coercion of the subtype embedding to a function is the subtype projection.
Finset.map_eq_empty.mpr
If a finset is empty, then its image under an embedding is also empty.
Finset.card_map
The cardinality of the image of a finset under an embedding equals the cardinality of the original finset.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v in a graph G if and only if v and w are adjacent in G.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The local recolouring criterion for peeling one vertex: the colour inserted at `v` must avoid `N(v)`'s colours and the colours of the other neighbours of `N(v)`, and `N(v)` must already satisfy the odd condition. -/theorem strong_odd_coloring_insert_vertex {V κ : Type} [Fintype V] [DecidableEq V]    [DecidableEq κ] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (g : V → κ)    (hout : is_strong_odd_coloring (G.induce {x | x ≠ v}) (fun x => g x.1))    (hproper : ∀ u ∈ G.neighborFinset v, g v ≠ g u)    (hfar : ∀ u ∈ G.neighborFinset v, ∀ w ∈ G.neighborFinset u, w ≠ v → g v ≠ g w)    (hpar : ∀ c : κ, {u ∈ G.neighborFinset v | g u = c} = ∅ ∨      Odd {u ∈ G.neighborFinset v | g u = c}.card) :    is_strong_odd_coloring G g := by  obtain ⟨hprop', hpar'⟩ := hout  refine ⟨?_, ?_⟩  · intro a b hab    by_cases ha : a = v    · subst ha      exact hproper b ((SimpleGraph.mem_neighborFinset _ _ _).mpr hab)    by_cases hb : b = v    · subst hb      exact (hproper a ((SimpleGraph.mem_neighborFinset _ _ _).mpr hab.symm)).symm    · exact hprop' (u := ⟨a, ha⟩) (v := ⟨b, hb⟩) hab  · intro x c    by_cases hx : x = v    · subst hx      exact hpar c    have hmap : (∀ u, G.Adj x u → g u = c → u ≠ v) →        (G.neighborFinset x).filter (fun u => g u = c) =        (((G.induce {y | y ≠ v}).neighborFinset ⟨x, hx⟩).filter          (fun u => g u.1 = c)).map (Function.Embedding.subtype _) := by      intro hnv      ext w      simp only [Finset.mem_filter, Finset.mem_map, Function.Embedding.coe_subtype]      constructor      · rintro ⟨hw, hwc⟩        have hw' : G.Adj x w := (SimpleGraph.mem_neighborFinset _ _ _).mp hw        exact ⟨⟨w, hnv w hw' hwc⟩, ⟨(SimpleGraph.mem_neighborFinset _ _ _).mpr hw', hwc⟩, rfl⟩      · rintro ⟨y, ⟨hy, hyc⟩, rfl⟩        have hy' : (G.induce {y | y ≠ v}).Adj ⟨x, hx⟩ y := (SimpleGraph.mem_neighborFinset _ _ _).mp hy        exact ⟨(SimpleGraph.mem_neighborFinset _ _ _).mpr hy', hyc⟩    have finish : (∀ u, G.Adj x u → g u = c → u ≠ v) →        ((G.neighborFinset x).filter (fun u => g u = c) = ∅ ∨          Odd ((G.neighborFinset x).filter (fun u => g u = c)).card) := by      intro hnv      rcases hpar' ⟨x, hx⟩ c with h | h      · left        rw [hmap hnv]        exact Finset.map_eq_empty.mpr h      · right        rw [hmap hnv, Finset.card_map]        exact h    by_cases hxv : G.Adj x v    · by_cases hc : g v = c      · right        have hone : (G.neighborFinset x).filter (fun u => g u = c) = {v} := by          ext w          simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_singleton]          constructor          · rintro ⟨hw, hwc⟩            by_contra hne            exact hfar x ((SimpleGraph.mem_neighborFinset _ _ _).mpr hxv.symm) w              ((SimpleGraph.mem_neighborFinset _ _ _).mpr hw) hne (hc.trans hwc.symm)          · rintro rfl            exact ⟨hxv, hc⟩        rw [hone, Finset.card_singleton]        exact odd_one      · exact finish fun u _ huc huv => hc (huv ▸ huc)    · exact finish fun u hu _ huv => hxv (huv ▸ hu)
See it in the graphDiscuss this resultChallenge it