The star sequence identifies all vertices of `l`: any two elements of `l` are
ProvedGraph.TwinWidth.starSequence_connectsaether-cataloggeometry
The star sequence identifies all vertices of l: any two elements of l are
related by the reflexive–transitive closure of the merge relation.
theorem Graph.TwinWidth.starSequence_connects{l : List V} {a b : V} (ha : a ∈ l) (hb : b ∈ l) :
Relation.ReflTransGen (MergeRel (starSequence l)) a b := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Geometry/Contractions.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Geometry/Contractions.lean
import Mathlib
import Definitions.Def_Geometry_Contractions
/-
Copyright (c) 2025 Harmonic. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aristotle (Harmonic)
-/
/-!
# Generic contraction sequences for twin-width
A *contraction sequence* of a graph repeatedly merges two vertices until a single
vertex remains. We model a contraction sequence abstractly as a list of merge
operations `seq : List (V × V)`, where the operation `(a, b)` identifies the two
super-vertices currently containing `a` and `b`.
Two pieces of data make such a list a genuine contraction sequence:
* every operation merges two *distinct* vertices (no self-reference), and
* the operations identify *all* vertices into one final super-vertex, i.e. the
reflexive–transitive closure of the merge relation is total on `V`.
This file develops the generic *star* contraction sequence built from a linear
ordering of the vertices, and proves the generic length bound
`twinWidth_contraction_bound`, which downstream files reuse instead of re-deriving.
-/
open Graph.TwinWidth
variable {V : Type*}Formal statement
theorem Graph.TwinWidth.starSequence_connects{l : List V} {a b : V} (ha : a ∈ l) (hb : b ∈ l) :
Relation.ReflTransGen (MergeRel (starSequence l)) a b := by sorrySource