finite_two_incidence_capacity_assignment
A finite incidence relation with two endpoints for every edge and at most d incident edges at every vertex, d at least two, admits an endpoint assignment with capacity d minus one.
Statement
theorem finite_two_incidence_capacity_assignment {E V : Type*} [Fintype E] [Fintype V] [DecidableEq V] (R : E → V → Prop) [DecidableRel R] (d : ℕ) (hd : 2 ≤ d) (he : ∀ e, (Finset.univ.filter (R e)).card = 2) (hv : ∀ v, (Finset.univ.filter (fun e => R e v)).card ≤ d) : ∃ f : E → V, (∀ e, R e (f e)) ∧ ∀ v, (Finset.univ.filter (fun e => f e = v)).card ≤ d - 1
- Source
- Helper for OP-494 in arXiv:2610.30174, following the additive-list coloring argument of arXiv:2302.02190v3, Corollary 5.3. Double-count incidences for every set of edges, apply finite matching to endpoint slots, and bound assignment fibers by the injective slot labels.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- simple_graph_exists_edge_tail_capacityEvery finite simple graph of maximum degree at least two admits an assignment of each edge to one of its endpoints, with at most…
The proof, explained
The proof reduces the vertex capacity constraint to Hall's Marriage Theorem by giving each vertex v a set of d - 1 distinct capacity slots (v, i) with i ∈ Fin(d - 1). For any edge subset s, its incident slots form the Cartesian product U × Fin(d - 1), where U is the set of endpoints of edges in s. Double counting incidences between s and U gives 2|s| ≤ d|U|, which implies |s| ≤ (d - 1)|U| using the hypothesis d ≥ 2, thus verifying Hall's marriage condition. Hall's Marriage Theorem then yields an injective assignment of edges to slots, whose vertex projection assigns each edge to an incident vertex while ensuring no vertex receives more than d - 1 edges.
To prove the theorem, it suffices to verify Hall's marriage condition for an auxiliary relation Q that pairs each edge with d - 1 virtual capacity slots per incident vertex.
Line 11 enables classical logic. Line 12 defines the relation Q(e, (v, i)) ↔ R(e, v) on E × (V × Fin (d - 1)), representing assigning an edge to an incident vertex along with one of its d - 1 capacity slots. Lines 13–14 state Hall's condition for Q: for every edge subset s ⊆ E, |s| ≤ |N_Q(s)|. Lines 15–16 fix an arbitrary edge subset s ⊆ E and define U ⊆ V to be the set of all endpoints of edges in s.
classical let Q : E → V × Fin (d - 1) → Prop := fun e p => R e p.1 have hall : ∀ s : Finset E, s.card ≤ (Finset.univ.filter (fun p : V × Fin (d - 1) => ∃ e ∈ s, Q e p)).card := by intro s let U : Finset V := Finset.univ.filter (fun v => ∃ e ∈ s, R e v)
For every edge e ∈ s, all of its incident vertices in V belong to U.
By definition of U, any vertex incident to an edge e ∈ s is contained in U. Therefore, the set of incident vertices of e restricted to U (Finset.bipartiteAbove R U e) is the same as the full set of vertices incident to e in V.
uses
Finset.bipartiteAbove,Finset.mem_filter,Finset.mem_univ,true_and,And.righthave hrow (e : E) (hes : e ∈ s) : U.bipartiteAbove R e = Finset.univ.filter (R e) := by ext v simp only [Finset.bipartiteAbove, Finset.mem_filter, Finset.mem_univ, true_and, U] exact ⟨And.right, fun h => ⟨⟨e, hes, h⟩, h⟩⟩
The number of edges in s and vertices in U satisfy the double-counting inequality 2|s| ≤ d|U|.
We count incidences between s and U using `Finset.card_nsmul_le_card_nsmul`. Each edge in s has degree 2 in U by the previous step and the hypothesis he. Each vertex in U has degree at most d in the full graph E by hv, and therefore at most d in s by subset inclusion. Double counting then gives 2|s| ≤ d|U|.
uses
smul_eq_mul,Finset.card_nsmul_le_card_nsmul,Finset.card_le_card,Finset.filter_subset_filter,Finset.subset_univhave hcount : s.card * 2 ≤ U.card * d := by simpa only [smul_eq_mul] using (Finset.card_nsmul_le_card_nsmul (R := ℕ) R (s := s) (t := U) (m := 2) (n := d) (fun e hes => by rw [hrow e hes, he e]; norm_num) (fun v _ => (Finset.card_le_card (Finset.filter_subset_filter _ (Finset.subset_univ s))).trans (hv v)))
The inequality |s| ≤ |U|(d - 1) holds.
Since d ≥ 2, we have d ≤ 2(d - 1) (by omega). Multiplying by |U| via `Nat.mul_le_mul_left` gives d|U| ≤ 2(d - 1)|U|. Combining this with 2|s| ≤ d|U| yields 2|s| ≤ 2(d - 1)|U|, which implies |s| ≤ |U|(d - 1) by non-linear arithmetic.
uses
Nat.mul_le_mul_lefthave hd' : d ≤ 2 * (d - 1) := by omega have hbound : s.card ≤ U.card * (d - 1) := by have := Nat.mul_le_mul_left U.card hd' nlinarith
Hall's condition holds for s: the number of edges |s| is at most the number of available slots incident to s.
The neighborhood of s under Q is the set of pairs (v, i) with v ∈ U and i ∈ Fin (d - 1), which is the Cartesian product U × Fin (d - 1). Its cardinality is |U| * (d - 1) by `Finset.card_product`. The bound |s| ≤ |U|(d - 1) established previously shows that Hall's condition is satisfied for s.
uses
Finset.card_producthave hslots : Finset.univ.filter (fun p : V × Fin (d - 1) => ∃ e ∈ s, Q e p) = U ×ˢ Finset.univ := by ext p simp [Q, U] rw [hslots, Finset.card_product] simpa using hbound
Hall's Marriage Theorem yields an injective assignment g : E → V × Fin (d - 1), from which we define the endpoint assignment f(e) = (g(e)).1.
Because Hall's condition holds for every edge subset s, Hall's Marriage Theorem for finite types (`Fintype.all_card_le_filter_rel_iff_exists_injective`) guarantees the existence of an injection g matching each edge e to an incident vertex slot (v, i). Defining f(e) = (g(e)).1 assigns each edge to an incident vertex, leaving only the vertex capacity condition to verify.
uses
Fintype.all_card_le_filter_rel_iff_exists_injectiveobtain ⟨g, hginj, hg⟩ := (Fintype.all_card_le_filter_rel_iff_exists_injective Q).mp hall refine ⟨fun e => (g e).1, hg, ?_⟩
Each vertex v ∈ V is assigned at most d - 1 edges by f, completing the proof.
For each vertex v, consider the set of edges assigned to v, {e | (g(e)).1 = v}. The projection to the slot index e ↦ (g(e)).2 maps this set into Fin (d - 1). This projection is injective: if two edges in the fiber have the same slot index, then both components of g agree, so g(e) = g(e') by `Prod.ext`, which implies e = e' by the injectivity of g. By `Finset.card_le_card_of_injOn`, the number of edges assigned to v is at most |Fin (d - 1)| = d - 1.
uses
Finset.card_le_card_of_injOn,Finset.mem_univ,Prod.ext,Finset.mem_filter.mpintro v calc (Finset.univ.filter (fun e => (g e).1 = v)).card ≤ (Finset.univ : Finset (Fin (d - 1))).card := by apply Finset.card_le_card_of_injOn (fun e => (g e).2) · intro e _; exact Finset.mem_univ _ · intro e he' e' he'' h apply hginj apply Prod.ext · exact (Finset.mem_filter.mp he').2.trans (Finset.mem_filter.mp he'').2.symm · exact h _ = d - 1 := by simp
Finset.bipartiteAbove- Given a relation r and a subset t, `bipartiteAbove r t a` is the set of elements b ∈ t such that r(a, b).
Finset.mem_filter- An element a belongs to `Finset.filter p s` if and only if a ∈ s and p(a) holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- Conjunction with True simplifies to the original proposition: (True ∧ p) = p.
And.right- From a conjunction a ∧ b, deduce the second conjunct b.
smul_eq_mul- Scalar multiplication on natural numbers is ordinary multiplication: a • b = a * b.
Finset.card_nsmul_le_card_nsmul- Double-counting lemma for relations: if every element of s has at least m neighbors in t, and every element of t has at most n neighbors in s, then |s| * m ≤ |t| * n.
Finset.card_le_card- If s ⊆ t for finsets s and t, then |s| ≤ |t|.
Finset.filter_subset_filter- Filtering respects subset inclusion: if s ⊆ t, then {x ∈ s | p(x)} ⊆ {x ∈ t | p(x)}.
Finset.subset_univ- Every finset in a finite type is a subset of `Finset.univ`.
Nat.mul_le_mul_left- Left-multiplication by a natural number preserves the order: if n ≤ m, then k * n ≤ k * m.
Finset.card_product- The cardinality of the Cartesian product of two finsets is the product of their cardinalities: |s × t| = |s| * |t|.
Fintype.all_card_le_filter_rel_iff_exists_injective- Hall's Marriage Theorem for finite types: an injective relation-preserving function exists if and only if every subset A satisfies |A| ≤ |N(A)|.
Finset.card_le_card_of_injOn- If a function maps s into t and is injective on s, then |s| ≤ |t|.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
Finset.mem_filter.mp- If a belongs to `Finset.filter p s`, then a ∈ s and p(a) holds.
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 BigOperatorstheorem finite_two_incidence_capacity_assignment {E V : Type*} [Fintype E] [Fintype V] [DecidableEq V] (R : E → V → Prop) [DecidableRel R] (d : ℕ) (hd : 2 ≤ d) (he : ∀ e, (Finset.univ.filter (R e)).card = 2) (hv : ∀ v, (Finset.univ.filter (fun e => R e v)).card ≤ d) : ∃ f : E → V, (∀ e, R e (f e)) ∧ ∀ v, (Finset.univ.filter (fun e => f e = v)).card ≤ d - 1 := by classical let Q : E → V × Fin (d - 1) → Prop := fun e p => R e p.1 have hall : ∀ s : Finset E, s.card ≤ (Finset.univ.filter (fun p : V × Fin (d - 1) => ∃ e ∈ s, Q e p)).card := by intro s let U : Finset V := Finset.univ.filter (fun v => ∃ e ∈ s, R e v) have hrow (e : E) (hes : e ∈ s) : U.bipartiteAbove R e = Finset.univ.filter (R e) := by ext v simp only [Finset.bipartiteAbove, Finset.mem_filter, Finset.mem_univ, true_and, U] exact ⟨And.right, fun h => ⟨⟨e, hes, h⟩, h⟩⟩ have hcount : s.card * 2 ≤ U.card * d := by simpa only [smul_eq_mul] using (Finset.card_nsmul_le_card_nsmul (R := ℕ) R (s := s) (t := U) (m := 2) (n := d) (fun e hes => by rw [hrow e hes, he e]; norm_num) (fun v _ => (Finset.card_le_card (Finset.filter_subset_filter _ (Finset.subset_univ s))).trans (hv v))) have hd' : d ≤ 2 * (d - 1) := by omega have hbound : s.card ≤ U.card * (d - 1) := by have := Nat.mul_le_mul_left U.card hd' nlinarith have hslots : Finset.univ.filter (fun p : V × Fin (d - 1) => ∃ e ∈ s, Q e p) = U ×ˢ Finset.univ := by ext p simp [Q, U] rw [hslots, Finset.card_product] simpa using hbound obtain ⟨g, hginj, hg⟩ := (Fintype.all_card_le_filter_rel_iff_exists_injective Q).mp hall refine ⟨fun e => (g e).1, hg, ?_⟩ intro v calc (Finset.univ.filter (fun e => (g e).1 = v)).card ≤ (Finset.univ : Finset (Fin (d - 1))).card := by apply Finset.card_le_card_of_injOn (fun e => (g e).2) · intro e _; exact Finset.mem_univ _ · intro e he' e' he'' h apply hginj apply Prod.ext · exact (Finset.mem_filter.mp he').2.trans (Finset.mem_filter.mp he'').2.symm · exact h _ = d - 1 := by simp