AFTD Auto-Formalizing Theoretical Domains

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

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