expand_vertex
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⟩ }