simple_graph_is_triangle_distinct_decidable
instance
For a finite graph, the proposition that the vertex triangle-degrees are pairwise distinct is decidable.
Statement
instance simple_graph_is_triangle_distinct_decidable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Decidable (simple_graph_is_triangle_distinct G)
- Source
- step towards exists_nonempty_regular_eight_triangle_distinct
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 2
- simple_graph_triangle_degreeThe triangle-degree td_G(v): the number of triangles of G containing v, i.e. the number of 2-element subsets {u, w} of the neighbourhood…
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- Used by 2
- eight_regular_triangle_distinct_certificateA computable boolean certificate checker for the regularity-8 witness problem: it returns true exactly when every one of the n vertices…
- eight_regular_triangle_distinct_of_certificateIf the computable certificate checker accepts the edge list L on the n vertices {0,…,n−1}, then the graph of L is 8-regular and has…
Lean source view module on GitHub
/-- Triangle-distinctness of a graph on a finite vertex type is decidable. -/ instance simple_graph_is_triangle_distinct_decidable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Decidable (simple_graph_is_triangle_distinct G) := inferInstanceAs (Decidable (Function.Injective (fun v => simple_graph_triangle_degree G v)))