AFTD Auto-Formalizing Theoretical Domains

expand_vertex

deforiginal

Given a graph J on vertex type V and a marked vertex s, the vertex expansion replaces s by an independent set of new vertices W, each adjacent to exactly the neighbors of s in J.

Statement

def expand_vertex {V W : Type*} (J : SimpleGraph V) (s : V) :
    SimpleGraph ({v : V // v ≠ s} ⊕ W)
Related work
folklore
Verified
13 Nov 2026
Axioms
none listed

Read back from the Lean

Given types V and W, a simple graph J on V, and a vertex s : V, expand_vertex defines a SimpleGraph on the vertex type {v : V // v ≠ s} ⊕ W (the disjoint sum of the subtype of vertices of V not equal to s, and W). In this graph: - Two vertices Sum.inl u and Sum.inl v (for u, v : {v : V // v ≠ s}) are adjacent if and only if u.val and v.val are adjacent in J; - A vertex Sum.inl u and a vertex Sum.inr w (for w : W) are adjacent if and only if u.val is adjacent to s in J; - Symmetrically, Sum.inr w and Sum.inl v are adjacent if and only if s is adjacent to v.val in J; - Two vertices Sum.inr w₁ and Sum.inr w₂ (for w₁, w₂ : W) are never adjacent (i.e., W forms an independent set).

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

/-- The simple graph obtained from J by replacing vertex s with an independent set W of vertices having the same neighborhood as s. -/
def expand_vertex {V W : Type*} (J : SimpleGraph V) (s : V) :
    SimpleGraph ({v : V // v ≠ s} ⊕ W) := {
  Adj := fun x y => match x, y with
    | Sum.inl u, Sum.inl v => J.Adj u.val v.val
    | Sum.inl u, Sum.inr _ => J.Adj u.val s
    | Sum.inr _, Sum.inl v => J.Adj s v.val
    | Sum.inr _, Sum.inr _ => False
  symm := ⟨by
    rintro (u | w) (v | z) h
    · exact J.adj_symm h
    · change J.Adj s u.val; exact J.adj_symm h
    · change J.Adj v.val s; exact J.adj_symm h
    · contradiction⟩
  loopless := ⟨by
    rintro (u | w) h
    · exact J.loopless.irrefl u.val h
    · contradiction⟩
}
See it in the graphDiscuss this resultChallenge it