AFTD Auto-Formalizing Theoretical Domains

finite_edge_packing_odd_incidence_bound

theoremverified

For a finite set of undirected edges E and a pairwise edge-disjoint family P of three-edge sets, if each member of P has even incidence at every vertex and every vertex in O has odd incidence in E, then 3|P| + ceil(|O|/2) ≤ |E|.

Statement

theorem finite_edge_packing_odd_incidence_bound {V : Type} [DecidableEq V]
    (E : Finset (Sym2 V)) (P : Finset (Finset (Sym2 V))) (O : Finset V)
    (hsub : ∀ t ∈ P, t ⊆ E)
    (hdisj : (P : Set (Finset (Sym2 V))).Pairwise Disjoint)
    (hsize : ∀ t ∈ P, t.card = 3)
    (heven : ∀ v : V, ∀ t ∈ P, Even ((t.filter (fun e => v ∈ e)).card))
    (hodd : ∀ v ∈ O, Odd ((E.filter (fun e => v ∈ e)).card)) :
    3 * P.card + (O.card + 1) / 2 ≤ E.card
Source
Odd-degree packing bound for ten_vertex_exchange_packing_upper.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof decomposes the edge set E into the union U = ⋃ P of the 3-edge sets in the packing and the remaining edges D = E \ U. Because the members of P are pairwise disjoint triples, |U| = 3|P| and every vertex has even degree in U. Any vertex in O has odd degree in E, so it must be incident to at least one edge of D, meaning O is covered by the endpoints of D. Since each edge has at most 2 endpoints, |O| ≤ 2|D| = 2(|E| - 3|P|), which rearranges to 3|P| + ⌈|O|/2⌉ ≤ |E|.

  1. Let U = ⋃ P and D = E \ U; then U ⊆ E.

    We partition the edges of E into U, the union of all 3-edge sets in the packing P, and D = E \ U, the leftover edges. Since every set t ∈ P is a subset of E by hypothesis hsub, every edge in U belongs to E, so U ⊆ E.

    lines 9–15

    uses Finset.mem_biUnion.mp

      classical
      let U : Finset (Sym2 V) := P.biUnion id
      let D : Finset (Sym2 V) := E \ U
      have hUE : U ⊆ E := by
        intro e he
        obtain ⟨t,ht,het⟩ := Finset.mem_biUnion.mp he
        exact hsub t ht het
  2. |U| = 3|P|.

    Since the elements of P are pairwise disjoint (hypothesis hdisj), the cardinality of their union U is the sum of their individual cardinalities (Finset.card_biUnion). Each set t ∈ P contains exactly 3 edges (hypothesis hsize), so the sum evaluates to 3|P| (Finset.sum_congr, Nat.mul_comm).

    lines 16–22

    uses Finset.card_biUnion, Finset.sum_congr, Nat.mul_comm

      have hpair : (P : Set (Finset (Sym2 V))).PairwiseDisjoint (fun t => t) := hdisj
      have hUcard : U.card = 3 * P.card := by
        change (P.biUnion fun t => t).card = 3 * P.card
        rw [Finset.card_biUnion hpair]
        calc
          _ = ∑ _t ∈ P, 3 := Finset.sum_congr rfl (fun t ht => hsize t ht)
          _ = 3 * P.card := by simp [Nat.mul_comm]
  3. Every vertex v ∈ V has even degree in U.

    The set of edges in U incident to v is the union over t ∈ P of edges in t incident to v (Finset.filter_biUnion). Because the sets in P are pairwise disjoint, these filtered sets remain pairwise disjoint (Finset.pairwiseDisjoint_filter), so the degree of v in U is the sum over t ∈ P of the degrees of v in t (Finset.card_biUnion). Each term is even by hypothesis heven, and a sum of even numbers is even (Finset.even_sum).

    lines 23–27

    uses Finset.filter_biUnion, Finset.card_biUnion, Finset.pairwiseDisjoint_filter, Finset.even_sum

      have hEvenU (v : V) : Even ((U.filter (fun e => v ∈ e)).card) := by
        dsimp only [U]
        change Even (((P.biUnion fun t => t).filter (fun e => v ∈ e)).card)
        rw [Finset.filter_biUnion, Finset.card_biUnion (Finset.pairwiseDisjoint_filter hpair (fun e => v ∈ e))]
        exact Finset.even_sum _ (fun t ht => heven v t ht)
  4. Every vertex in O is incident to at least one edge of D, so O ⊆ ⋃_{e ∈ D} e.

    Suppose, for contradiction, that some v ∈ O is not incident to any edge in D. Then every edge of E incident to v must avoid D = E \ U, meaning it must belong to U. Since U ⊆ E, the edges of E incident to v coincide exactly with the edges of U incident to v (Finset.Subset.antisymm). Consequently, the degree of v in E equals its degree in U, which is even. But this contradicts the assumption that v ∈ O has odd degree in E (hypothesis hodd, Nat.not_even_iff_odd.mpr). Hence every v ∈ O is incident to some edge e ∈ D (Finset.mem_biUnion.mpr, Sym2.mem_toFinset.mpr).

    lines 28–49

    uses Finset.mem_biUnion.mpr, Sym2.mem_toFinset.mpr, Finset.Subset.antisymm, Finset.mem_filter.mp, Finset.mem_sdiff.mpr, Finset.mem_filter.mpr, Nat.not_even_iff_odd.mpr

      have hCover : O ⊆ D.biUnion (fun e => e.toFinset) := by
        intro v hv
        by_contra hn
        have hno : ∀ e ∈ D, v ∉ e := by
          intro e he hve
          apply hn
          exact Finset.mem_biUnion.mpr ⟨e,he,Sym2.mem_toFinset.mpr hve⟩
        have hEq : E.filter (fun e => v ∈ e) = U.filter (fun e => v ∈ e) := by
          apply Finset.Subset.antisymm
          · intro e he
            obtain ⟨heE,hve⟩ := Finset.mem_filter.mp he
            have heU : e ∈ U := by
              by_contra hnot
              exact hno e (Finset.mem_sdiff.mpr ⟨heE,hnot⟩) hve
            exact Finset.mem_filter.mpr ⟨heU,hve⟩
          · intro e he
            obtain ⟨heU,hve⟩ := Finset.mem_filter.mp he
            exact Finset.mem_filter.mpr ⟨hUE heU,hve⟩
        have hne : ¬Even ((E.filter (fun e => v ∈ e)).card) := Nat.not_even_iff_odd.mpr (hodd v hv)
        apply hne
        rw [hEq]
        exact hEvenU v
  5. |O| ≤ 2|D|.

    Since O is covered by the endpoints of edges in D, its cardinality is bounded by the union of the endpoint sets (Finset.card_le_card), which is bounded by the sum of endpoint set sizes ∑_{e ∈ D} |e| (Finset.card_biUnion_le). Each undirected edge e has at most 2 distinct endpoints (Sym2.card_toFinset), so each term is at most 2 (Finset.sum_le_sum). Summing 2 over D gives 2|D| (Nat.mul_comm).

    lines 50–59

    uses Finset.card_le_card, Finset.card_biUnion_le, Finset.sum_le_sum, Sym2.card_toFinset, Nat.mul_comm

      have hcard : O.card ≤ 2 * D.card := by
        calc
          O.card ≤ (D.biUnion (fun e => e.toFinset)).card := Finset.card_le_card hCover
          _ ≤ ∑ e ∈ D, (e.toFinset).card := Finset.card_biUnion_le
          _ ≤ ∑ _e ∈ D, 2 := by
            apply Finset.sum_le_sum
            intro e he
            rw [Sym2.card_toFinset]
            split_ifs <;> omega
          _ = 2 * D.card := by simp [Nat.mul_comm]
  6. 3|P| + ⌈|O|/2⌉ ≤ |E|. automation

    Since U ⊆ E, the size of D = E \ U is |E| - |U| = |E| - 3|P| (Finset.card_sdiff_of_subset). Substituting this into |O| ≤ 2|D| gives |O| ≤ 2(|E| - 3|P|), which rearranges to 3|P| + (|O| + 1)/2 ≤ |E|. The linear integer arithmetic tactic omega verifies this rearrangement.

    lines 60–62

    uses Finset.card_sdiff_of_subset, Finset.card_le_card

      have hDcard : D.card = E.card - U.card := Finset.card_sdiff_of_subset hUE
      have hle : U.card ≤ E.card := Finset.card_le_card hUE
      omega
Finset.card_biUnion
The cardinality of the union of a pairwise disjoint family of finite sets equals the sum of the cardinalities of the sets.
Finset.card_biUnion_le
The cardinality of a union of finite sets is at most the sum of the cardinalities of the sets.
Finset.card_le_card
A subset of a finite set has cardinality less than or equal to the ambient set.
Finset.card_sdiff_of_subset
For a subset s ⊆ t of a finite set, the cardinality of the difference t \ s is |t| - |s|.
Finset.even_sum
A finite sum of even numbers is even.
Finset.filter_biUnion
Filtering a union of finite sets by a predicate equals the union of the filtered sets.
Finset.mem_biUnion.mp
An element of the union of a family of finite sets belongs to at least one set in the family.
Finset.mem_biUnion.mpr
An element belonging to some set in a family of finite sets belongs to the union of that family.
Finset.mem_filter.mp
An element of a filtered finite set belongs to the set and satisfies the filtering predicate.
Finset.mem_filter.mpr
An element of a finite set satisfying a predicate belongs to the filtered set.
Finset.mem_sdiff.mpr
An element belonging to s and not to t belongs to s \ t.
Finset.pairwiseDisjoint_filter
Filtering each set in a pairwise disjoint family preserves pairwise disjointness.
Finset.Subset.antisymm
Two finite sets are equal if each is a subset of the other.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree everywhere.
Finset.sum_le_sum
If each term in a finite sum is bounded by the corresponding term in another sum, the total sum is bounded by the other total sum.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Nat.not_even_iff_odd.mpr
An odd natural number is not even.
Sym2.card_toFinset
The number of distinct vertices in an undirected edge is 1 if it is a self-loop and 2 otherwise.
Sym2.mem_toFinset.mpr
A vertex incident to an undirected edge belongs to the finite set of that edge's endpoints.

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

theorem finite_edge_packing_odd_incidence_bound {V : Type} [DecidableEq V]    (E : Finset (Sym2 V)) (P : Finset (Finset (Sym2 V))) (O : Finset V)    (hsub : ∀ t ∈ P, t ⊆ E)    (hdisj : (P : Set (Finset (Sym2 V))).Pairwise Disjoint)    (hsize : ∀ t ∈ P, t.card = 3)    (heven : ∀ v : V, ∀ t ∈ P, Even ((t.filter (fun e => v ∈ e)).card))    (hodd : ∀ v ∈ O, Odd ((E.filter (fun e => v ∈ e)).card)) :    3 * P.card + (O.card + 1) / 2 ≤ E.card := by  classical  let U : Finset (Sym2 V) := P.biUnion id  let D : Finset (Sym2 V) := E \ U  have hUE : U ⊆ E := by    intro e he    obtain ⟨t,ht,het⟩ := Finset.mem_biUnion.mp he    exact hsub t ht het  have hpair : (P : Set (Finset (Sym2 V))).PairwiseDisjoint (fun t => t) := hdisj  have hUcard : U.card = 3 * P.card := by    change (P.biUnion fun t => t).card = 3 * P.card    rw [Finset.card_biUnion hpair]    calc      _ = ∑ _t ∈ P, 3 := Finset.sum_congr rfl (fun t ht => hsize t ht)      _ = 3 * P.card := by simp [Nat.mul_comm]  have hEvenU (v : V) : Even ((U.filter (fun e => v ∈ e)).card) := by    dsimp only [U]    change Even (((P.biUnion fun t => t).filter (fun e => v ∈ e)).card)    rw [Finset.filter_biUnion, Finset.card_biUnion (Finset.pairwiseDisjoint_filter hpair (fun e => v ∈ e))]    exact Finset.even_sum _ (fun t ht => heven v t ht)  have hCover : O ⊆ D.biUnion (fun e => e.toFinset) := by    intro v hv    by_contra hn    have hno : ∀ e ∈ D, v ∉ e := by      intro e he hve      apply hn      exact Finset.mem_biUnion.mpr ⟨e,he,Sym2.mem_toFinset.mpr hve⟩    have hEq : E.filter (fun e => v ∈ e) = U.filter (fun e => v ∈ e) := by      apply Finset.Subset.antisymm      · intro e he        obtain ⟨heE,hve⟩ := Finset.mem_filter.mp he        have heU : e ∈ U := by          by_contra hnot          exact hno e (Finset.mem_sdiff.mpr ⟨heE,hnot⟩) hve        exact Finset.mem_filter.mpr ⟨heU,hve⟩      · intro e he        obtain ⟨heU,hve⟩ := Finset.mem_filter.mp he        exact Finset.mem_filter.mpr ⟨hUE heU,hve⟩    have hne : ¬Even ((E.filter (fun e => v ∈ e)).card) := Nat.not_even_iff_odd.mpr (hodd v hv)    apply hne    rw [hEq]    exact hEvenU v  have hcard : O.card ≤ 2 * D.card := by    calc      O.card ≤ (D.biUnion (fun e => e.toFinset)).card := Finset.card_le_card hCover      _ ≤ ∑ e ∈ D, (e.toFinset).card := Finset.card_biUnion_le      _ ≤ ∑ _e ∈ D, 2 := by        apply Finset.sum_le_sum        intro e he        rw [Sym2.card_toFinset]        split_ifs <;> omega      _ = 2 * D.card := by simp [Nat.mul_comm]  have hDcard : D.card = E.card - U.card := Finset.card_sdiff_of_subset hUE  have hle : U.card ≤ E.card := Finset.card_le_card hUE  omega
See it in the graphDiscuss this resultChallenge it