finite_edge_packing_odd_incidence_bound
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
- ten_vertex_exchange_packing_upperThe witness has no packing of eleven edge-disjoint triangles.
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|.
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.
uses
Finset.mem_biUnion.mpclassical 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
|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).
uses
Finset.card_biUnion,Finset.sum_congr,Nat.mul_commhave 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]
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).
uses
Finset.filter_biUnion,Finset.card_biUnion,Finset.pairwiseDisjoint_filter,Finset.even_sumhave 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)
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).
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.mprhave 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
|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).
uses
Finset.card_le_card,Finset.card_biUnion_le,Finset.sum_le_sum,Sym2.card_toFinset,Nat.mul_commhave 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]
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.
uses
Finset.card_sdiff_of_subset,Finset.card_le_cardhave 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.
- The ceiling division ⌈|O|/2⌉ is represented in Lean's natural-number division as `(O.card + 1) / 2`.
- The final arithmetic deduction is performed automatically by the `omega` decision procedure.
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.
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