AFTD Auto-Formalizing Theoretical Domains

finite_two_incidence_capacity_assignment

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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.

    lines 11–16

      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)
  2. 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.

    lines 17–21

    uses Finset.bipartiteAbove, Finset.mem_filter, Finset.mem_univ, true_and, And.right

        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⟩⟩
  3. 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|.

    lines 22–27

    uses smul_eq_mul, Finset.card_nsmul_le_card_nsmul, Finset.card_le_card, Finset.filter_subset_filter, Finset.subset_univ

        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)))
  4. 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.

    lines 28–31

    uses Nat.mul_le_mul_left

        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
  5. 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.

    lines 32–37

    uses Finset.card_product

        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
  6. 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.

    lines 38–40

    uses Fintype.all_card_le_filter_rel_iff_exists_injective

      obtain ⟨g, hginj, hg⟩ :=
        (Fintype.all_card_le_filter_rel_iff_exists_injective Q).mp hall
      refine ⟨fun e => (g e).1, hg, ?_⟩
  7. 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.

    lines 41–52

    uses Finset.card_le_card_of_injOn, Finset.mem_univ, Prod.ext, Finset.mem_filter.mp

      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
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

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
See it in the graphDiscuss this resultChallenge it