simple_graph_of_edge_list_decidable_rel
instance
Adjacency in the graph determined by an edge list is decidable.
Statement
instance simple_graph_of_edge_list_decidable_rel {n : ℕ} (L : List (Fin n × Fin n)) :
DecidableRel (simple_graph_of_edge_list L).Adj- Source
- step towards exists_nonempty_regular_eight_triangle_distinct
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_of_edge_listThe simple graph on {0,…,n−1} whose edges are the unordered pairs occurring in the list L (a pair (a, b) in L contributes the edge {a, b},…
- 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
/-- Adjacency of a graph given by an edge list is decidable, so its triangle-degrees compute. -/ instance simple_graph_of_edge_list_decidable_rel {n : ℕ} (L : List (Fin n × Fin n)) : DecidableRel (simple_graph_of_edge_list L).Adj := inferInstanceAs (DecidableRel (SimpleGraph.fromRel (fun a b : Fin n => (a, b) ∈ L)).Adj)