strong_odd_coloring_insert_vertex
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.
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.
obtain ⟨hprop', hpar'⟩ := hout refine ⟨?_, ?_⟩
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'.
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
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.
· intro x c by_cases hx : x = v · subst hx exact hpar c
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.
uses
Function.Embedding.subtype,Finset.mem_filter,Finset.mem_map,Function.Embedding.coe_subtype,SimpleGraph.mem_neighborFinsethave 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⟩
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.
uses
Finset.map_eq_empty.mpr,Finset.card_maphave 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
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).
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.mem_singleton,Finset.card_singleton,odd_oneby_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
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.
· 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)