galvin_bipartite_multigraph_list_edge_colouring_two
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
uses
Set.mem_insert_iff,Set.mem_singleton_iffby_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]
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.
uses
Set.ncard_le_ncard,Set.toFinite,Set.ncard_insert_of_notMem,Set.ncard_pairhave 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
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₂.
uses
dif_pos,Classical.choose_spec,galvin_bipartite_multigraph_list_edge_colouring_two_unique_other,Ne.symmhave 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
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.
uses
Classical.choose_spec,galvin_bipartite_multigraph_list_edge_colouring_two_involution_eq_of_ne,dif_negintro 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]
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 α.
uses
galvin_bipartite_multigraph_list_edge_colouring_two_involution_involutiveset 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 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.
uses
list_colorable_two_of_two_involutions,Set.toFiniteobtain ⟨c, hcL, hc_ne⟩ := list_colorable_two_of_two_involutions (Set.univ : Set α) (Set.toFinite _) p q hp hq L (fun e _ => hL e)
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.
refine ⟨c, fun e => hcL e trivial, fun γ => ⟨?_, ?_⟩⟩
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₂) = γ.
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
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₂) = γ.
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.
- The fibre involution is defined using noncomputable choice (`Classical.choose`), but the uniqueness lemma ensures that whenever another element exists in a fibre of size at most 2, it is unique.
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.
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