AFTD Auto-Formalizing Theoretical Domains

has_induced_k4_subdivision

def

A graph G contains an induced subdivision of K4: there are four distinct branch vertices and one simple path for each of their six unordered pairs. No branch vertex is internal to a path; distinct paths share only branch vertices; and every G-edge between vertices of their union is an edge of one of the paths.

Statement

def has_induced_k4_subdivision {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2610.32404, definition of ISK4-freeness and Lemma 11.1. The standard induced subdivision is encoded by six paths with disjoint interiors whose union is induced.
Verified
27 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

For a simple graph $G$ with vertex type $V$, has_induced_k4_subdivision G asserts that $G$ contains an induced subdivision of $K_4$. Specifically, there exist: 1. An injective map $b : \mathrm{Fin}\ 4 \to V$ (the four branch vertices), and 2. A family of walks $P$ indexed by pairs $e = (i, j) \in \mathrm{Fin}\ 4 \times \mathrm{Fin}\ 4$ with $i < j$, such that each $P(e)$ is a walk in $G$ from $b(i)$ to $b(j)$, satisfying: - Each walk $P(e)$ is a path (contains no repeated vertices). - For every pair $e$ and index $i \in \mathrm{Fin}\ 4$, if the branch vertex $b(i)$ belongs to the support (vertex set) of $P(e)$, then $i$ is an endpoint of $e$ (i.e., $i = e.1$ or $i = e.2$). - For any two distinct pairs $e \neq f$ and any vertex $v \in V$, if $v$ is in the support of $P(e)$ and in the support of $P(f)$, then $v$ is a branch vertex (there exists $i \in \mathrm{Fin}\ 4$ such that $v = b(i)$). - For any vertices $x, y \in V$, if $x$ belongs to the support of some path $P(e)$ and $y$ belongs to the support of some path $P(e')$, and $x$ and $y$ are adjacent in $G$, then the undirected edge $s(x, y)$ belongs to the edge set of some path $P(e'')$ (i.e., the subgraph induced by the vertices of the subdivision has no edges other than those of the paths).

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

/-- Contains an induced subdivision of K4, encoded by six internally disjoint simple paths between four distinct branch vertices, with no extra edges on their union. -/
def has_induced_k4_subdivision {V : Type*} (G : SimpleGraph V) : Prop :=
∃ (b : Fin 4 → V), Function.Injective b ∧
    ∃ (P : (e : {ij : Fin 4 × Fin 4 // ij.1 < ij.2}) →
      G.Walk (b e.val.1) (b e.val.2)),
      (∀ e, (P e).IsPath) ∧
      (∀ e i, b i ∈ (P e).support → i = e.val.1 ∨ i = e.val.2) ∧
      (∀ e f, e ≠ f → ∀ v, v ∈ (P e).support → v ∈ (P f).support →
        ∃ i, v = b i) ∧
      (∀ x y, (∃ e, x ∈ (P e).support) → (∃ e, y ∈ (P e).support) →
        G.Adj x y → ∃ e, s(x, y) ∈ (P e).edges)
See it in the graphDiscuss this resultChallenge it