AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_of_avoided_near_high_codegree

theoremverified

If a maximum triangle packing avoids an edge with at least twice the packing number minus one common neighbors and the packing number is at least two, the triangle cover number is at most twice the packing number.

Statement

theorem simple_graph_triangle_cover_of_avoided_near_high_codegree
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v)
    (hcl : ∀ t ∈ P, G.IsNClique 3 t)
    (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card)
    (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s))
    (hsize : P.card = simple_graph_triangle_packing_number G)
    (hPtwo : 2 ≤ P.card)
    (hlarge : 2 * P.card ≤
      ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card + 1) :
    simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G
Source
Structural helper for the triangle packing-cover campaign, related to matching-cover reductions in https://arxiv.org/abs/2610.15269; see state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof applies simple_graph_common_neighbors_matching_of_avoided_packing to find a matching M of pairs in the common neighborhood N of u and v such that |N| ≤ |P| + |M|. Using the lower bound |N| ≥ 2|P| - 1, we extract a sub-matching M₀ ⊆ M of size |P| - 1, which covers at most 2|P| - 2 vertices and thus leaves an uncovered common neighbor w ∈ N ∖ ⋃ M₀. Finally, simple_graph_triangle_cover_of_near_full_common_matching bounds the cover number by |M₀| + 3 = |P| + 2, which is at most 2|P| = 2ν(G) since |P| ≥ 2.

  1. There exists a pairwise disjoint collection M of 2-element cliques in the common neighborhood of u and v with |P| - 1 ≤ |M|.

    Let N be the set of common neighbors of u and v. By simple_graph_common_neighbors_matching_of_avoided_packing, there is a pairwise disjoint family M of pairs of adjacent vertices in N (forming triangles with both u and v) such that |N| ≤ |P| + |M|. Since 2|P| ≤ |N| + 1 by hypothesis, linear arithmetic implies |P| - 1 ≤ |M|.

    lines 16–20

    uses simple_graph_common_neighbors_matching_of_avoided_packing

      classical
      let N : Finset V := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)
      obtain ⟨M, hMdis, hMprop, hMbound⟩ :=
        simple_graph_common_neighbors_matching_of_avoided_packing G u v P huv hcl hmax havoid
      have hsubcard : P.card - 1 ≤ M.card := by omega
  2. There exists a sub-matching M₀ ⊆ M of size |P| - 1 consisting of pairwise disjoint pairs.

    Since |P| - 1 ≤ |M|, Finset.exists_subset_card_eq guarantees the existence of a subset M₀ ⊆ M of cardinality |P| - 1. Because M₀ is a subset of the pairwise disjoint family M, the pairs in M₀ are also pairwise disjoint.

    lines 21–24

    uses Finset.exists_subset_card_eq

      obtain ⟨M0, hM0sub, hM0card⟩ := Finset.exists_subset_card_eq hsubcard
      have hM0dis : (M0 : Set (Finset V)).Pairwise Disjoint := by
        intro e he f hf hef
        exact hMdis (hM0sub he) (hM0sub hf) hef
  3. The union of the pairs in M₀ contains at most 2|M₀| vertices.

    By Finset.card_biUnion_le, the size of the union ⋃ M₀ is bounded by the sum of the cardinalities of the sets in M₀. Since each set e ∈ M₀ has size 2, summing 2 over M₀ gives 2|M₀| by Finset.sum_le_sum, le_of_eq, and Nat.mul_comm.

    lines 25–32

    uses Finset.card_biUnion_le, Finset.sum_le_sum, le_of_eq, Nat.mul_comm

      have hUcard : (M0.biUnion id).card ≤ 2 * M0.card := by
        calc
          (M0.biUnion id).card ≤ ∑ e ∈ M0, e.card := Finset.card_biUnion_le
          _ ≤ ∑ _e ∈ M0, 2 := by
            apply Finset.sum_le_sum
            intro e he
            exact le_of_eq (hMprop e (hM0sub he)).1
          _ = 2 * M0.card := by simp [Nat.mul_comm]
  4. The common neighborhood N is not contained in ⋃ M₀.

    If N ⊆ ⋃ M₀, then by Finset.card_le_card, |N| ≤ |⋃ M₀| ≤ 2|M₀| = 2(|P| - 1). But 2|P| ≤ |N| + 1 implies 2|P| ≤ 2|P| - 1, a contradiction by linear arithmetic.

    lines 33–38

    uses Finset.card_le_card

      have hnot : ¬N ⊆ M0.biUnion id := by
        intro hs
        have hh := Finset.card_le_card hs
        change 2 * P.card ≤ N.card + 1 at hlarge
        rw [hM0card] at hUcard
        omega
  5. There exists a common neighbor w ∈ N not in ⋃ M₀, and every pair in M₀ avoids w while retaining its clique and neighborhood properties.

    Since N is not a subset of ⋃ M₀, Finset.not_subset.mp yields a vertex w ∈ N with w ∉ ⋃ M₀. By Finset.mem_filter.mp, w is adjacent to both u and v. Each pair e ∈ M₀ inherits from M the property of consisting of two adjacent common neighbors of u and v. Furthermore, w ∉ e, since otherwise w ∈ ⋃ M₀ by Finset.mem_biUnion.mpr.

    lines 39–49

    uses Finset.not_subset.mp, Finset.mem_filter.mp, Finset.mem_biUnion.mpr

      obtain ⟨w, hwN, hwU⟩ := Finset.not_subset.mp hnot
      have hw' : G.Adj u w ∧ G.Adj v w := (Finset.mem_filter.mp hwN).2
      have hM0prop : ∀ e ∈ M0, e.card = 2 ∧ w ∉ e ∧
          (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧
          (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by
        intro e he
        have hp := hMprop e (hM0sub he)
        refine ⟨hp.1, ?_, hp.2⟩
        intro hw
        apply hwU
        exact Finset.mem_biUnion.mpr ⟨e, he, hw⟩
  6. The triangle packing number of G equals |M₀| + 1.

    Since |M₀| = |P| - 1 and |P| is the triangle packing number of G, rearranging gives ν(G) = |M₀| + 1.

    lines 50–52

      have hnum : simple_graph_triangle_packing_number G = M0.card + 1 := by
        rw [hM0card, ← hsize]
        omega
  7. The triangle cover number of G is at most 2 * simple_graph_triangle_packing_number G.

    Applying simple_graph_triangle_cover_of_near_full_common_matching to u, v, w, and M₀ yields τ(G) ≤ |M₀| + 3. Substituting |M₀| = |P| - 1 gives τ(G) ≤ |P| + 2. Because |P| ≥ 2, linear arithmetic gives |P| + 2 ≤ 2|P| = 2ν(G).

    lines 53–56

    uses simple_graph_triangle_cover_of_near_full_common_matching

      have hc := simple_graph_triangle_cover_of_near_full_common_matching G u v w M0
        huv hw'.1 hw'.2 hM0prop hM0dis hnum
      rw [hM0card] at hc
      omega
simple_graph_common_neighbors_matching_of_avoided_packing
If a maximum triangle packing P avoids the edge uv, there exists a pairwise disjoint set M of 2-element cliques in the common neighborhood of u and v such that the number of common neighbors of u and v is at most |P| + |M|.
Finset.exists_subset_card_eq
If n ≤ |s| for a finite set s, there exists a subset t ⊆ s with |t| = n.
Finset.card_biUnion_le
The cardinality of a union of a family of finite sets is at most the sum of the cardinalities of the sets.
Finset.sum_le_sum
A sum indexed by a finite set is bounded above by the sum of pointwise upper bounds.
le_of_eq
An equality a = b implies the inequality a ≤ b.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.not_subset.mp
If s is not a subset of t, there exists an element x ∈ s with x ∉ t.
Finset.mem_filter.mp
If an element belongs to the filter of a finite set by a predicate, it belongs to the set and satisfies the predicate.
Finset.mem_biUnion.mpr
If x belongs to some set in a family, then x belongs to the union of that family.
simple_graph_triangle_cover_of_near_full_common_matching
In a graph where edge uv has a common neighbor w and a disjoint matching M of size 2 in the common neighborhood disjoint from w, if the triangle packing number is |M| + 1, then the triangle cover number is at most |M| + 3.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_triangle_cover_of_avoided_near_high_codegree    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v)    (hcl : ∀ t ∈ P, G.IsNClique 3 t)    (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card)    (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s))    (hsize : P.card = simple_graph_triangle_packing_number G)    (hPtwo : 2 ≤ P.card)    (hlarge : 2 * P.card ≤      ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card + 1) :    simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G := by  classical  let N : Finset V := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)  obtain ⟨M, hMdis, hMprop, hMbound⟩ :=    simple_graph_common_neighbors_matching_of_avoided_packing G u v P huv hcl hmax havoid  have hsubcard : P.card - 1 ≤ M.card := by omega  obtain ⟨M0, hM0sub, hM0card⟩ := Finset.exists_subset_card_eq hsubcard  have hM0dis : (M0 : Set (Finset V)).Pairwise Disjoint := by    intro e he f hf hef    exact hMdis (hM0sub he) (hM0sub hf) hef  have hUcard : (M0.biUnion id).card ≤ 2 * M0.card := by    calc      (M0.biUnion id).card ≤ ∑ e ∈ M0, e.card := Finset.card_biUnion_le      _ ≤ ∑ _e ∈ M0, 2 := by        apply Finset.sum_le_sum        intro e he        exact le_of_eq (hMprop e (hM0sub he)).1      _ = 2 * M0.card := by simp [Nat.mul_comm]  have hnot : ¬N ⊆ M0.biUnion id := by    intro hs    have hh := Finset.card_le_card hs    change 2 * P.card ≤ N.card + 1 at hlarge    rw [hM0card] at hUcard    omega  obtain ⟨w, hwN, hwU⟩ := Finset.not_subset.mp hnot  have hw' : G.Adj u w ∧ G.Adj v w := (Finset.mem_filter.mp hwN).2  have hM0prop : ∀ e ∈ M0, e.card = 2 ∧ w ∉ e ∧      (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧      (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by    intro e he    have hp := hMprop e (hM0sub he)    refine ⟨hp.1, ?_, hp.2⟩    intro hw    apply hwU    exact Finset.mem_biUnion.mpr ⟨e, he, hw⟩  have hnum : simple_graph_triangle_packing_number G = M0.card + 1 := by    rw [hM0card, ← hsize]    omega  have hc := simple_graph_triangle_cover_of_near_full_common_matching G u v w M0    huv hw'.1 hw'.2 hM0prop hM0dis hnum  rw [hM0card] at hc  omega
See it in the graphDiscuss this resultChallenge it