AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_subset_of_separator

theoremverified

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.

  1. 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.

    lines 8–10

    uses not_or, Finset.not_subset

      by_contra h
      rw [not_or, Finset.not_subset, Finset.not_subset] at h
      obtain ⟨⟨x, hxt, hxA⟩, ⟨y, hyt, hyB⟩⟩ := h
  2. 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.

    lines 11–15

    uses Finset.mem_univ, Finset.mem_union.mp

      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
  3. The vertex y belongs to A.

    Similarly, y must be in A ∪ B. Because y ∉ B, it must belong to A.

    lines 16–20

    uses Finset.mem_univ, Finset.mem_union.mp

      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
  4. The vertices y and x are distinct (y ≠ x).

    If y = x, then y ∈ A would imply x ∈ A, which contradicts x ∉ A.

    lines 21–23

      have hxy : y ≠ x := by
        rintro rfl
        exact hxA hyA
  5. 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.

    lines 24–25

    uses Finset.mem_sdiff.mpr

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it