AFTD Auto-Formalizing Theoretical Domains

galvin_bipartite_multigraph_list_edge_colouring_two

theoremverified

The k = 2 case of Galvin's list edge colouring theorem in fibre form: if every fibre of f and every fibre of g has at most two elements (the bipartite multigraph has maximum degree at most 2, so it is a disjoint union of paths and even cycles), then lists of size at least two admit a proper list edge colouring, i.e. a choice c e ∈ L e with each colour class meeting every fibre of f and of g at most once.

Statement

theorem galvin_bipartite_multigraph_list_edge_colouring_two {α : Type*} [Finite α] (f g : α → ℕ)
    (hf : ∀ γ : ℕ, {e | f e = γ}.ncard ≤ 2) (hg : ∀ γ : ℕ, {e | g e = γ}.ncard ≤ 2)
    (L : α → Finset ℕ) (hL : ∀ e : α, 2 ≤ (L e).card) :
    ∃ c : α → ℕ, (∀ e : α, c e ∈ L e) ∧
      ∀ γ : ℕ, (∀ e₁ e₂ : α, c e₁ = γ → c e₂ = γ → f e₁ = f e₂ → e₁ = e₂) ∧
        ∀ e₁ e₂ : α, c e₁ = γ → c e₂ = γ → g e₁ = g e₂ → e₁ = e₂
Source
step towards matroid_sbo_common_list_chromatic_eq
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • list_colorable_two_of_two_involutionsLet E be a finite set and p, q two involutions; they define two unit-capacity partition matroids on E with classes {e, p e} and {e, q e}…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The theorem reduces list edge colouring of a bipartite multigraph with maximum degree at most 2 to list colouring with respect to two involutions. Because each fibre of f and g has at most two elements, each vertex map defines an involution on edges that swaps the at most two edges incident to that vertex. Applying `list_colorable_two_of_two_involutions` on the entire edge set yields a choice of colours from lists of size at least 2 such that no non-trivial orbit of either involution is monochromatic. Since any two distinct edges sharing an f-value or g-value are swapped by the corresponding involution, they necessarily receive distinct colours, ensuring that every colour class meets each fibre at most once.

  1. Assume for contradiction that two elements x and y in the fibre of e are distinct; then the 3-element set {e, x, y} is a subset of that fibre.

    To prove x = y, we assume for contradiction that x ≠ y. Since x ≠ e, y ≠ e, and both have f-value equal to f(e), each of e, x, and y belongs to the fibre {z | f z = f e}. Checking membership element by element confirms that {e, x, y} is contained in the fibre.

    lines 10–17

    uses Set.mem_insert_iff, Set.mem_singleton_iff

      by_contra hxy
      have h_sub : ({e, x, y} : Set α) ⊆ {z | f z = f e} := by
        intro z hz
        simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hz
        rcases hz with rfl | rfl | rfl
        · simp
        · simp [hfx]
        · simp [hfy]
  2. The set {e, x, y} has cardinality 3, contradicting the assumption that each fibre has cardinality at most 2.

    Because e ∉ {x, y} and x ≠ y, the cardinality of {e, x, y} is 1 + 2 = 3 by `Set.ncard_insert_of_notMem` and `Set.ncard_pair`. By subset monotonicity of cardinality (`Set.ncard_le_ncard`), the fibre must have at least 3 elements, contradicting the hypothesis that every fibre has cardinality at most 2.

    lines 18–24

    uses Set.ncard_le_ncard, Set.toFinite, Set.ncard_insert_of_notMem, Set.ncard_pair

      have h_card := Set.ncard_le_ncard h_sub (Set.toFinite _)
      have hbc_fin : ({x, y} : Set α).Finite := Set.toFinite _
      have ha : e ∉ ({x, y} : Set α) := by simp [hxe.symm, hye.symm]
      have h_eq : ({e, x, y} : Set α) = insert e ({x, y} : Set α) := rfl
      rw [h_eq, Set.ncard_insert_of_notMem ha hbc_fin, Set.ncard_pair hxy] at h_card
      have hf_le := hf (f e)
      linarith
  3. If e₁ ≠ e₂ and f(e₁) = f(e₂), then the fibre involution applied to e₁ evaluates to e₂.

    The element e₂ witnesses the existence of a distinct element in the same fibre. Unfolding the definition of the involution, the conditional branch is satisfied (`dif_pos`), so the involution returns `Classical.choose h`. By `Classical.choose_spec` and the uniqueness lemma `galvin_bipartite_multigraph_list_edge_colouring_two_unique_other`, this chosen element must equal e₂.

    lines 29–33

    uses dif_pos, Classical.choose_spec, galvin_bipartite_multigraph_list_edge_colouring_two_unique_other, Ne.symm

      have h : ∃ e', e' ≠ e₁ ∧ f e' = f e₁ := ⟨e₂, Ne.symm hne, hf_eq.symm⟩
      change (if h : ∃ e', e' ≠ e₁ ∧ f e' = f e₁ then Classical.choose h else e₁) = e₂
      rw [dif_pos h]
      have h_spec := Classical.choose_spec h
      exact galvin_bipartite_multigraph_list_edge_colouring_two_unique_other f hf e₁ (Classical.choose h) e₂ h_spec.1 (Ne.symm hne) h_spec.2 hf_eq.symm
  4. The fibre map is an involution on α.

    For any element e, we evaluate the involution twice by splitting on whether there exists another element in the fibre (`split_ifs`). If a distinct partner exists, applying the involution once selects it, and applying it a second time returns e by `galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne`. If no other element exists, the negative branch (`dif_neg`) leaves e fixed both times.

    lines 38–44

    uses Classical.choose_spec, galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne, dif_neg

      intro e
      change galvin_bipartite_multigraph_list_edge_colouring_two_involution f (if h : ∃ e', e' ≠ e ∧ f e' = f e then Classical.choose h else e) = e
      split_ifs with h
      · have h_spec := Classical.choose_spec h
        exact galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne f hf h_spec.1 h_spec.2
      · change (if h' : ∃ e', e' ≠ e ∧ f e' = f e then Classical.choose h' else e) = e
        rw [dif_neg h]
  5. Define the fibre involutions p and q for f and g, and verify that they are involutive.

    We define p and q as the fibre involutions for f and g respectively. By `galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive`, both p and q are involutive functions on α.

    lines 53–56

    uses galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive

      set p := galvin_bipartite_multigraph_list_edge_colouring_two_involution f
      set q := galvin_bipartite_multigraph_list_edge_colouring_two_involution g
      have hp : Function.Involutive p := galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive f hf
      have hq : Function.Involutive q := galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive g hg
  6. Obtain a list colouring c from the two-involutions theorem such that c(e) ∈ L(e) and c(p(e)) ≠ c(e), c(q(e)) ≠ c(e) whenever an involution moves e.

    Applying `list_colorable_two_of_two_involutions` to the universal set with involutions p and q and list sizes at least 2 yields a valid colouring c.

    lines 57–58

    uses list_colorable_two_of_two_involutions, Set.toFinite

      obtain ⟨c, hcL, hc_ne⟩ := list_colorable_two_of_two_involutions (Set.univ : Set α)
        (Set.toFinite _) p q hp hq L (fun e _ => hL e)
  7. The colouring c assigns each edge a colour from its list, reducing the theorem to showing injectivity on the fibres of f and g.

    We supply c as the witness; the list membership condition holds immediately, leaving two subgoals asserting that colour classes meet each fibre of f and g at most once.

    line 59

      refine ⟨c, fun e => hcL e trivial, fun γ => ⟨?_, ?_⟩⟩
  8. The colouring c is injective on each fibre of f: no two distinct edges with the same f-value receive the same colour.

    Suppose e₁ and e₂ have the same colour γ and f(e₁) = f(e₂). If e₁ ≠ e₂, then p(e₁) = e₂ by `galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne`, so p(e₁) ≠ e₁. But c separates non-fixed points of p, giving c(e₂) ≠ c(e₁), contradicting c(e₁) = c(e₂) = γ.

    lines 60–66

    uses galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne, Ne.symm

      · intro e₁ e₂ hc1 hc2 hf_eq
        by_contra hne
        have hp_eq : p e₁ = e₂ := galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne f hf hne hf_eq
        have hp_ne : p e₁ ≠ e₁ := by rw [hp_eq]; exact Ne.symm hne
        have hc_diff := (hc_ne e₁ trivial).1 trivial hp_ne
        rw [hp_eq, hc1, hc2] at hc_diff
        exact hc_diff rfl
  9. The colouring c is injective on each fibre of g: no two distinct edges with the same g-value receive the same colour.

    Similarly, if e₁ and e₂ share colour γ and have g(e₁) = g(e₂), assuming e₁ ≠ e₂ implies q(e₁) = e₂ and q(e₁) ≠ e₁; the involution separation property of c then yields c(e₂) ≠ c(e₁), which contradicts c(e₁) = c(e₂) = γ.

    lines 67–73

    uses galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne, Ne.symm

      · intro e₁ e₂ hc1 hc2 hg_eq
        by_contra hne
        have hq_eq : q e₁ = e₂ := galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne g hg hne hg_eq
        have hq_ne : q e₁ ≠ e₁ := by rw [hq_eq]; exact Ne.symm hne
        have hc_diff := (hc_ne e₁ trivial).2 trivial hq_ne
        rw [hq_eq, hc1, hc2] at hc_diff
        exact hc_diff rfl
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff
An element belongs to the singleton {b} if and only if it equals b.
Set.ncard_le_ncard
If s is a subset of a finite set t, then the cardinality of s is at most that of t.
Set.toFinite
A subset of a finite type is finite.
Set.ncard_insert_of_notMem
Inserting an element not in a finite set s increases its cardinality by 1.
Set.ncard_pair
A pair of distinct elements has cardinality 2.
dif_pos
A dependent conditional evaluates to its then-branch when the condition holds.
dif_neg
A dependent conditional evaluates to its else-branch when the condition is false.
Classical.choose_spec
The witness produced by classical choice satisfies the property stated in the existential hypothesis.
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
galvin_bipartite_multigraph_list_edge_colouring_two_unique_other
In any fibre of size at most 2, there is at most one element distinct from a given element.
galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne
If two distinct elements share the same fibre of size at most 2, the fibre involution maps one to the other.
galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive
The fibre involution swapping pairs of elements in fibres of size at most 2 is an involution.
list_colorable_two_of_two_involutions
Given two involutions on a finite set and lists of size at least 2, there exists a list colouring separating any element from its image under both involutions whenever they differ.

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

open scoped Classicalnoncomputable def galvin_bipartite_multigraph_list_edge_colouring_two_involution {α : Type*} (f : α → ℕ) (e : α) : α :=  if h : ∃ e' : α, e' ≠ e ∧ f e' = f e then Classical.choose h else elemma galvin_bipartite_multigraph_list_edge_colouring_two_unique_other {α : Type*} [Finite α] (f : α → ℕ)    (hf : ∀ γ : ℕ, {e | f e = γ}.ncard ≤ 2) (e x y : α)    (hxe : x ≠ e) (hye : y ≠ e) (hfx : f x = f e) (hfy : f y = f e) :    x = y := by  by_contra hxy  have h_sub : ({e, x, y} : Set α) ⊆ {z | f z = f e} := by    intro z hz    simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hz    rcases hz with rfl | rfl | rfl    · simp    · simp [hfx]    · simp [hfy]  have h_card := Set.ncard_le_ncard h_sub (Set.toFinite _)  have hbc_fin : ({x, y} : Set α).Finite := Set.toFinite _  have ha : e ∉ ({x, y} : Set α) := by simp [hxe.symm, hye.symm]  have h_eq : ({e, x, y} : Set α) = insert e ({x, y} : Set α) := rfl  rw [h_eq, Set.ncard_insert_of_notMem ha hbc_fin, Set.ncard_pair hxy] at h_card  have hf_le := hf (f e)  linarithlemma galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne {α : Type*} [Finite α] (f : α → ℕ)    (hf : ∀ γ : ℕ, {e | f e = γ}.ncard ≤ 2) {e₁ e₂ : α} (hne : e₁ ≠ e₂) (hf_eq : f e₁ = f e₂) :    galvin_bipartite_multigraph_list_edge_colouring_two_involution f e₁ = e₂ := by  have h : ∃ e', e' ≠ e₁ ∧ f e' = f e₁ := ⟨e₂, Ne.symm hne, hf_eq.symm⟩  change (if h : ∃ e', e' ≠ e₁ ∧ f e' = f e₁ then Classical.choose h else e₁) = e₂  rw [dif_pos h]  have h_spec := Classical.choose_spec h  exact galvin_bipartite_multigraph_list_edge_colouring_two_unique_other f hf e₁ (Classical.choose h) e₂ h_spec.1 (Ne.symm hne) h_spec.2 hf_eq.symmlemma galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive {α : Type*} [Finite α] (f : α → ℕ)    (hf : ∀ γ : ℕ, {e | f e = γ}.ncard ≤ 2) :    Function.Involutive (galvin_bipartite_multigraph_list_edge_colouring_two_involution f) := by  intro e  change galvin_bipartite_multigraph_list_edge_colouring_two_involution f (if h : ∃ e', e' ≠ e ∧ f e' = f e then Classical.choose h else e) = e  split_ifs with h  · have h_spec := Classical.choose_spec h    exact galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne f hf h_spec.1 h_spec.2  · change (if h' : ∃ e', e' ≠ e ∧ f e' = f e then Classical.choose h' else e) = e    rw [dif_neg h]/-- The maximum-degree-two case of Galvin's theorem, in fibre form. -/theorem galvin_bipartite_multigraph_list_edge_colouring_two {α : Type*} [Finite α] (f g : α → ℕ)    (hf : ∀ γ : ℕ, {e | f e = γ}.ncard ≤ 2) (hg : ∀ γ : ℕ, {e | g e = γ}.ncard ≤ 2)    (L : α → Finset ℕ) (hL : ∀ e : α, 2 ≤ (L e).card) :    ∃ c : α → ℕ, (∀ e : α, c e ∈ L e) ∧      ∀ γ : ℕ, (∀ e₁ e₂ : α, c e₁ = γ → c e₂ = γ → f e₁ = f e₂ → e₁ = e₂) ∧        ∀ e₁ e₂ : α, c e₁ = γ → c e₂ = γ → g e₁ = g e₂ → e₁ = e₂ := by  set p := galvin_bipartite_multigraph_list_edge_colouring_two_involution f  set q := galvin_bipartite_multigraph_list_edge_colouring_two_involution g  have hp : Function.Involutive p := galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive f hf  have hq : Function.Involutive q := galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutive g hg  obtain ⟨c, hcL, hc_ne⟩ := list_colorable_two_of_two_involutions (Set.univ : Set α)    (Set.toFinite _) p q hp hq L (fun e _ => hL e)  refine ⟨c, fun e => hcL e trivial, fun γ => ⟨?_, ?_⟩⟩  · intro e₁ e₂ hc1 hc2 hf_eq    by_contra hne    have hp_eq : p e₁ = e₂ := galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne f hf hne hf_eq    have hp_ne : p e₁ ≠ e₁ := by rw [hp_eq]; exact Ne.symm hne    have hc_diff := (hc_ne e₁ trivial).1 trivial hp_ne    rw [hp_eq, hc1, hc2] at hc_diff    exact hc_diff rfl  · intro e₁ e₂ hc1 hc2 hg_eq    by_contra hne    have hq_eq : q e₁ = e₂ := galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne g hg hne hg_eq    have hq_ne : q e₁ ≠ e₁ := by rw [hq_eq]; exact Ne.symm hne    have hc_diff := (hc_ne e₁ trivial).2 trivial hq_ne    rw [hq_eq, hc1, hc2] at hc_diff    exact hc_diff rfl
See it in the graphDiscuss this resultChallenge it