simple_graph_triangle_cover_of_two_star_packings
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
- simple_graph_triangle_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
- Used by 2
- simple_graph_triangle_cover_of_full_common_matchingIf an edge common-neighbor graph has a matching as large as the graph triangle packing number, the triangle cover number is at most the…
- simple_graph_triangle_cover_of_near_full_common_matchingIf an edge has a common-neighbor matching of size one below the graph triangle packing number and another common neighbor outside the…
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.
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.
classical let F : Finset (Sym2 V) := insert s(u,v) CEvery 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.
uses
Finset.mem_insert.mphave 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
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.
uses
Finset.mem_insert_of_memhave 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⟩
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.
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
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.
uses
Finset.one_lt_card.mp,Finset.mem_inter.mp,Sym2.mem_iffhave 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
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.
uses
Finset.mem_insert_self,Sym2.mem_iffrefine ⟨s(u,v), Finset.mem_insert_self _ _, ?_⟩ intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> assumption
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.
uses
Nat.sInf_le,Nat.add_comm,Finset.card_insert_lecalc 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
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.
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)