AFTD Auto-Formalizing Theoretical Domains

simple_graph_add_apex

deforiginal

Given a simple graph G on vertex type V and a set of vertices S ⊆ V, simple_graph_add_apex G S is the simple graph on Option V obtained by adjoining a new apex vertex (none) that is adjacent precisely to the vertices some v for v ∈ S, while preserving all edges of G on the original vertices.

Statement

def simple_graph_add_apex {V : Type*} (G : SimpleGraph V) (S : Set V) : SimpleGraph (Option V)
Related work
arXiv:2611.06626 Section 2.4
Verified
05 Nov 2026
Axioms
none listed

Read back from the Lean

simple_graph_add_apex is a definition that takes a type V, a simple graph G on V, and a subset S : Set V, and constructs a SimpleGraph (Option V) using SimpleGraph.fromRel applied to the binary relation R on Option V defined by: - R (some u) (some v) = G.Adj u v for all u, v : V - R none (some v) = (v ∈ S) for all v : V - R (some u) none = (u ∈ S) for all u : V - R none none = False.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Add an apex vertex (none) connected to vertices in S to a simple graph G on V. -/
def simple_graph_add_apex {V : Type*} (G : SimpleGraph V) (S : Set V) : SimpleGraph (Option V) :=
  SimpleGraph.fromRel fun
    | some u, some v => G.Adj u v
    | none, some v => v ∈ S
    | some u, none => u ∈ S
    | none, none => False
See it in the graphDiscuss this resultChallenge it