simple_graph_triangle_subset_of_separator
If vertex subsets A and B cover V and have no edges between A \ B and B \ A, then every triangle of G is contained entirely in A or entirely in B.
Statement
theorem simple_graph_triangle_subset_of_separator {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (A B : Finset V) (hcover : A ∪ B = Finset.univ) (hcross : ∀ x ∈ A \ B, ∀ y ∈ B \ A, ¬ G.Adj x y) (t : Finset V) (ht : G.IsNClique 3 t) : t ⊆ A ∨ t ⊆ B
- Source
- step towards simple_graph_triangle_cover_of_two_vertex_separator_induction
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by contradiction. Assuming the triangle t is contained in neither A nor B, we obtain vertices x ∈ t \ A and y ∈ t \ B. Since A and B cover all vertices, these must satisfy x ∈ B \ A and y ∈ A \ B, which also forces x ≠ y. But since t is a clique, x and y must be adjacent, directly contradicting the assumption that there are no edges between A \ B and B \ A.
Assume for contradiction that t is neither a subset of A nor of B, yielding vertices x ∈ t with x ∉ A and y ∈ t with y ∉ B.
We assume the negation ¬(t ⊆ A ∨ t ⊆ B). By De Morgan's laws and the definition of subset non-inclusion, this means there exist x ∈ t with x ∉ A and y ∈ t with y ∉ B.
uses
not_or,Finset.not_subsetby_contra h rw [not_or, Finset.not_subset, Finset.not_subset] at h obtain ⟨⟨x, hxt, hxA⟩, ⟨y, hyt, hyB⟩⟩ := h
The vertex x belongs to B.
Since A and B cover the entire vertex set, x must be in A ∪ B. Because x ∉ A, it must belong to B.
uses
Finset.mem_univ,Finset.mem_union.mphave hxB : x ∈ B := by have : x ∈ A ∪ B := hcover ▸ Finset.mem_univ x rcases Finset.mem_union.mp this with h | h · exact absurd h hxA · exact h
The vertex y belongs to A.
Similarly, y must be in A ∪ B. Because y ∉ B, it must belong to A.
uses
Finset.mem_univ,Finset.mem_union.mphave hyA : y ∈ A := by have : y ∈ A ∪ B := hcover ▸ Finset.mem_univ y rcases Finset.mem_union.mp this with h | h · exact h · exact absurd h hyB
The vertices y and x are distinct (y ≠ x).
If y = x, then y ∈ A would imply x ∈ A, which contradicts x ∉ A.
have hxy : y ≠ x := by rintro rfl exact hxA hyA
The vertices y and x are adjacent, producing a contradiction.
Because t is a 3-clique, any two distinct vertices in t are connected by an edge, so y and x are adjacent. But y ∈ A \ B and x ∈ B \ A, which contradicts the hypothesis that there are no edges between A \ B and B \ A.
uses
Finset.mem_sdiff.mprhave hadj : G.Adj y x := ht.1 hyt hxt hxy exact hcross y (Finset.mem_sdiff.mpr ⟨hyA, hyB⟩) x (Finset.mem_sdiff.mpr ⟨hxB, hxA⟩) hadj
not_or- The negation of a disjunction p ∨ q is equivalent to ¬p ∧ ¬q.
Finset.mem_sdiff.mpr- An element is in the set difference s \ t if it is in s and not in t.
Finset.mem_univ- Every element of a finite type belongs to the universal set univ.
Finset.mem_union.mp- If an element belongs to the union s ∪ t, then it belongs to s or to t.
Finset.not_subset- A set s is not a subset of t if and only if there exists an element x ∈ s such that x ∉ t.
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.
/-- If vertex subsets A and B cover V and have no edges between A \ B and B \ A, then every triangle of G is contained entirely in A or entirely in B. -/theorem simple_graph_triangle_subset_of_separator {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (A B : Finset V) (hcover : A ∪ B = Finset.univ) (hcross : ∀ x ∈ A \ B, ∀ y ∈ B \ A, ¬ G.Adj x y) (t : Finset V) (ht : G.IsNClique 3 t) : t ⊆ A ∨ t ⊆ B := by by_contra h rw [not_or, Finset.not_subset, Finset.not_subset] at h obtain ⟨⟨x, hxt, hxA⟩, ⟨y, hyt, hyB⟩⟩ := h have hxB : x ∈ B := by have : x ∈ A ∪ B := hcover ▸ Finset.mem_univ x rcases Finset.mem_union.mp this with h | h · exact absurd h hxA · exact h have hyA : y ∈ A := by have : y ∈ A ∪ B := hcover ▸ Finset.mem_univ y rcases Finset.mem_union.mp this with h | h · exact h · exact absurd h hyB have hxy : y ≠ x := by rintro rfl exact hxA hyA have hadj : G.Adj y x := ht.1 hyt hxt hxy exact hcross y (Finset.mem_sdiff.mpr ⟨hyA, hyB⟩) x (Finset.mem_sdiff.mpr ⟨hxB, hxA⟩) hadj