AFTD Auto-Formalizing Theoretical Domains

add_apex_edges

deforiginal

Given a graph G on vertex type V and a subset of vertices T ⊆ V, add_apex_edges G T is the simple graph on Option V whose vertices are V ∪ {none}, retaining all edges of G on V and having edges between none and each vertex in T.

Statement

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

Read back from the Lean

Given a type V, a simple graph G on V, and a subset T : Set V, add_apex_edges G T is the simple graph on the vertex type Option V whose adjacency relation is defined as follows: - Two original vertices some u and some v are adjacent if and only if u and v are adjacent in G (G.Adj u v). - The new apex vertex none and an original vertex some t are adjacent (in either order) if and only if t ∈ T. - The new apex vertex none is not adjacent to itself.

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

/-- Graph on Option V extending G by an apex vertex adjacent to the vertices in T. -/
def add_apex_edges {V : Type*} (G : SimpleGraph V) (T : Set V) : SimpleGraph (Option V) := {
  Adj := fun x y =>
    match x, y with
    | some u, some v => G.Adj u v
    | none, some t => t ∈ T
    | some t, none => t ∈ T
    | none, none => False
  symm := ⟨by rintro (u | _) (v | _) h <;> simp_all [G.adj_symm]⟩
  loopless := ⟨by rintro (u | _) h <;> simp_all⟩
}
See it in the graphDiscuss this resultChallenge it