AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_edge_family_mem

theoremverified

A set of three edges belongs to the triangle edge family of G iff it is the set of non-diagonal pairs spanned by some three vertices forming a triangle of G.

Statement

theorem simple_graph_triangle_edge_family_mem {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (t : Finset (Sym2 V)) :
    t ∈ simple_graph_triangle_edge_family G ↔
      ∃ x : Finset V, G.IsNClique 3 x ∧ finite_vertex_set_edge_encoding x = t
Source
step towards simple_graph_high_degree_stable_point_irreducible_forced_exchange_barrier_counterexample
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

The proof, explained

The theorem is proved by unfolding the definition of the triangle edge family and simplifying the resulting set membership predicate. By definition, the triangle edge family is the image under the edge-encoding map of the 3-cliques filtered from the universal finset of vertex subsets. Applying standard rewrite rules for finset images, filters, and universal sets immediately reduces membership of an edge set t to the existence of a 3-clique whose edge encoding is t.

  1. A set of edges t belongs to the triangle edge family of G if and only if there exists a 3-clique x in G such that the non-diagonal edge encoding of x is t.

    By definition, simple_graph_triangle_edge_family G is the image under finite_vertex_set_edge_encoding of all vertex sets in Finset.univ that form a 3-clique in G. An element t belongs to this image iff it is the encoding of some vertex set x in that filtered set (Finset.mem_image). Membership in the filter requires x ∈ Finset.univ and G.IsNClique 3 x (Finset.mem_filter); since x ∈ Finset.univ is always true (Finset.mem_univ), this conjunction simplifies directly to G.IsNClique 3 x (true_and).

    lines 5–6

    uses simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and

      classical
      simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and]
simple_graph_triangle_edge_family
The definition of the triangle edge family of a graph G as the image under finite_vertex_set_edge_encoding of the 3-cliques of G in Finset.univ.
Finset.mem_image
An element b belongs to the image of a finset s under f if and only if there is some a ∈ s with f(a) = b.
Finset.mem_filter
An element a belongs to the filter of a finset s by predicate p if and only if a ∈ s and p(a) holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
Conjunction with True simplifies away: (True ∧ p) is equivalent to p.

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

/-- Membership in the triangle edge family: a three-edge set is the edge set of a triangle iff it is the non-diagonal pair set of some 3-clique. -/theorem simple_graph_triangle_edge_family_mem {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (t : Finset (Sym2 V)) :    t ∈ simple_graph_triangle_edge_family G ↔      ∃ x : Finset V, G.IsNClique 3 x ∧ finite_vertex_set_edge_encoding x = t := by  classical  simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and]
See it in the graphDiscuss this resultChallenge it