simple_graph_triangle_edge_family_mem
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
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- Used by 2
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
- simple_graph_seven_packing_local_minimum_seed_supergraph_rigidityA graph on the nine vertices of the local-exchange seed that contains all seed edges and has triangle packing number at most seven adds no…
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.
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).
uses
simple_graph_triangle_edge_family,Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_andclassical 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.
- The proof opens with `classical` to provide decidability instances for finset membership, filter, and image operations, a formal type-theoretic requirement with no paper counterpart.
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.
/-- 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]