AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_of_two_star_packings

theoremverified

Two triangle-maximal families whose non-star edges lie in C give a triangle cover of size at most |C|+1 if their star centers are adjacent.

Statement

theorem simple_graph_triangle_cover_of_two_star_packings
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (u v : V) (P Q : Finset (Finset V)) (C : Finset (Sym2 V))
    (huv : G.Adj u v)
    (hC : ∀ e ∈ C, e ∈ G.edgeSet)
    (hPmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card)
    (hQmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ Q, 2 ≤ (s ∩ t).card)
    (hPstar : ∀ s ∈ P, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → a = u ∨ b = u ∨ s(a,b) ∈ C)
    (hQstar : ∀ s ∈ Q, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → a = v ∨ b = v ∨ s(a,b) ∈ C) :
    simple_graph_triangle_cover_number G ≤ C.card + 1
Source
Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

To bound the triangle cover number of G, we consider the edge set F = C ∪ {uv}. If a triangle t contains an edge of C, it is already covered by F. Otherwise, because t shares at least two vertices with members of the families P and Q whose non-star edges are confined to C, the triangle t must contain both star centers u and v, and is therefore covered by the edge uv ∈ F. Since F is a valid triangle cover of G with size at most |C| + 1, the triangle cover number is at most |C| + 1.

  1. Define F as the edge set obtained by adding the edge uv to C.

    We work in classical logic and form the candidate edge cover F = C ∪ {uv} by inserting the unordered pair s(u, v) into the set C.

    lines 15–16

      classical
      let F : Finset (Sym2 V) := insert s(u,v) C
  2. Every edge in F is an edge of the graph G.

    For any e ∈ F, Finset.mem_insert.mp shows that either e = uv or e ∈ C. If e = uv, it is an edge of G by hypothesis huv; if e ∈ C, it is an edge of G by hypothesis hC.

    lines 17–21

    uses Finset.mem_insert.mp

      have hFedge : ∀ e ∈ F, e ∈ G.edgeSet := by
        intro e he
        rcases Finset.mem_insert.mp he with rfl | he
        · exact huv
        · exact hC e he
  3. If a triangle t contains an edge of C, then it contains an edge of F.

    Given any triangle (3-clique) t, we case-split on whether there is an edge e ∈ C with both endpoints in t. If such an edge exists, it belongs to F by Finset.mem_insert_of_mem, so t is covered by F.

    lines 22–26

    uses Finset.mem_insert_of_mem

      have hFcover : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t := by
        intro t ht
        by_cases hCT : ∃ e ∈ C, ∀ x ∈ e, x ∈ t
        · obtain ⟨e, he, ht⟩ := hCT
          exact ⟨e, Finset.mem_insert_of_mem he, ht⟩
  4. If a triangle t contains no edge of C, then u ∈ t.

    Assume t contains no edge of C. By hypothesis hPmax, t intersects some set s ∈ P in at least two vertices. By Finset.one_lt_card.mp, there exist distinct vertices a, b ∈ s ∩ t. By hypothesis hPstar, either a = u, b = u, or s(a, b) ∈ C. If s(a, b) ∈ C, its endpoints a, b ∈ t would mean t contains an edge of C, a contradiction. Hence either a = u or b = u, and since a, b ∈ t, this forces u ∈ t.

    lines 27–42

    uses Finset.one_lt_card.mp, Finset.mem_inter.mp, Sym2.mem_iff

        · have hu : u ∈ t := by
            obtain ⟨s, hs, hst⟩ := hPmax t ht
            obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hst
            have ha' := Finset.mem_inter.mp ha
            have hb' := Finset.mem_inter.mp hb
            rcases hPstar s hs a ha'.1 b hb'.1 hab with rfl | rfl | he
            · exact ha'.2
            · exact hb'.2
            · exfalso
              apply hCT
              refine ⟨s(a,b), he, ?_⟩
              intro x hx
              rw [Sym2.mem_iff] at hx
              rcases hx with rfl | rfl
              · exact ha'.2
              · exact hb'.2
  5. If a triangle t contains no edge of C, then v ∈ t.

    Symmetrically, hypothesis hQmax guarantees a set s ∈ Q intersecting t in at least two vertices. Finset.one_lt_card.mp yields two distinct vertices in s ∩ t, and hypothesis hQstar implies that either one of them is v or their edge lies in C. Since t contains no edge of C, Sym2.mem_iff rules out the edge case, which leaves v ∈ t.

    lines 43–58

    uses Finset.one_lt_card.mp, Finset.mem_inter.mp, Sym2.mem_iff

          have hv : v ∈ t := by
            obtain ⟨s, hs, hst⟩ := hQmax t ht
            obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hst
            have ha' := Finset.mem_inter.mp ha
            have hb' := Finset.mem_inter.mp hb
            rcases hQstar s hs a ha'.1 b hb'.1 hab with rfl | rfl | he
            · exact ha'.2
            · exact hb'.2
            · exfalso
              apply hCT
              refine ⟨s(a,b), he, ?_⟩
              intro x hx
              rw [Sym2.mem_iff] at hx
              rcases hx with rfl | rfl
              · exact ha'.2
              · exact hb'.2
  6. Any triangle t containing no edge of C contains the edge uv ∈ F, so F covers all triangles of G.

    Because both u ∈ t and v ∈ t, every vertex of the unordered pair s(u, v) belongs to t by Sym2.mem_iff. Since s(u, v) ∈ F by Finset.mem_insert_self, F covers t in this case as well.

    lines 59–62

    uses Finset.mem_insert_self, Sym2.mem_iff

          refine ⟨s(u,v), Finset.mem_insert_self _ _, ?_⟩
          intro x hx
          rw [Sym2.mem_iff] at hx
          rcases hx with rfl | rfl <;> assumption
  7. The triangle cover number of G is at most |C| + 1.

    By definition, the triangle cover number is the infimum of the sizes of valid triangle covers in G. Since F consists of graph edges and covers all triangles, Nat.sInf_le shows that the cover number is bounded above by |F|. Finally, Finset.card_insert_le and commutativity of addition (Nat.add_comm) give |F| ≤ |C| + 1.

    lines 63–65

    uses Nat.sInf_le, Nat.add_comm, Finset.card_insert_le

      calc
        simple_graph_triangle_cover_number G ≤ F.card := Nat.sInf_le ⟨F, hFedge, hFcover, rfl⟩
        _ ≤ C.card + 1 := by simpa [F, Nat.add_comm] using (Finset.card_insert_le s(u,v) C)
Finset.mem_insert.mp
An element in insert(a, s) is equal to a or belongs to s.
Finset.mem_insert_of_mem
If an element belongs to s, then it also belongs to insert(a, s).
Finset.one_lt_card.mp
If a finite set has cardinality greater than 1 (at least 2), it contains two distinct elements.
Finset.mem_inter.mp
If an element belongs to an intersection s₁ ∩ s₂, it belongs to both s₁ and s₂.
Sym2.mem_iff
A vertex x belongs to the unordered pair s(a, b) if and only if x = a or x = b.
Finset.mem_insert_self
An element a belongs to insert(a, s).
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1: |insert(a, s)| ≤ |s| + 1.

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_two_star_packings    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (u v : V) (P Q : Finset (Finset V)) (C : Finset (Sym2 V))    (huv : G.Adj u v)    (hC : ∀ e ∈ C, e ∈ G.edgeSet)    (hPmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card)    (hQmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ Q, 2 ≤ (s ∩ t).card)    (hPstar : ∀ s ∈ P, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → a = u ∨ b = u ∨ s(a,b) ∈ C)    (hQstar : ∀ s ∈ Q, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → a = v ∨ b = v ∨ s(a,b) ∈ C) :    simple_graph_triangle_cover_number G ≤ C.card + 1 := by  classical  let F : Finset (Sym2 V) := insert s(u,v) C  have hFedge : ∀ e ∈ F, e ∈ G.edgeSet := by    intro e he    rcases Finset.mem_insert.mp he with rfl | he    · exact huv    · exact hC e he  have hFcover : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t := by    intro t ht    by_cases hCT : ∃ e ∈ C, ∀ x ∈ e, x ∈ t    · obtain ⟨e, he, ht⟩ := hCT      exact ⟨e, Finset.mem_insert_of_mem he, ht⟩    · have hu : u ∈ t := by        obtain ⟨s, hs, hst⟩ := hPmax t ht        obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hst        have ha' := Finset.mem_inter.mp ha        have hb' := Finset.mem_inter.mp hb        rcases hPstar s hs a ha'.1 b hb'.1 hab with rfl | rfl | he        · exact ha'.2        · exact hb'.2        · exfalso          apply hCT          refine ⟨s(a,b), he, ?_⟩          intro x hx          rw [Sym2.mem_iff] at hx          rcases hx with rfl | rfl          · exact ha'.2          · exact hb'.2      have hv : v ∈ t := by        obtain ⟨s, hs, hst⟩ := hQmax t ht        obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hst        have ha' := Finset.mem_inter.mp ha        have hb' := Finset.mem_inter.mp hb        rcases hQstar s hs a ha'.1 b hb'.1 hab with rfl | rfl | he        · exact ha'.2        · exact hb'.2        · exfalso          apply hCT          refine ⟨s(a,b), he, ?_⟩          intro x hx          rw [Sym2.mem_iff] at hx          rcases hx with rfl | rfl          · exact ha'.2          · exact hb'.2      refine ⟨s(u,v), Finset.mem_insert_self _ _, ?_⟩      intro x hx      rw [Sym2.mem_iff] at hx      rcases hx with rfl | rfl <;> assumption  calc    simple_graph_triangle_cover_number G ≤ F.card := Nat.sInf_le ⟨F, hFedge, hFcover, rfl⟩    _ ≤ C.card + 1 := by simpa [F, Nat.add_comm] using (Finset.card_insert_le s(u,v) C)
See it in the graphDiscuss this resultChallenge it