AFTD Auto-Formalizing Theoretical Domains

is_induced_minor

def

A graph H is an induced minor of G if there exists an induced minor model of H in G, which maps each vertex of H to a connected vertex set in G such that branch sets are pairwise disjoint and adjacency between distinct branch sets matches adjacency in H.

Statement

def is_induced_minor {V_H V_G : Type*} (H : SimpleGraph V_H) (G : SimpleGraph V_G) : Prop
Defined in
arXiv:2611.09627:348
Verified
09 Nov 2026
Axioms
none listed
Used by 1
  • is_induced_minor_induceIf H is an induced minor of G, then for any subset A of vertices of H, the induced subgraph H[A] is also an induced minor of G.

Read back from the Lean

For simple graphs $H$ on vertex type $V_H$ and $G$ on vertex type $V_G$, is_induced_minor H G asserts that there exists a family of subsets of $V_G$ indexed by $V_H$, $X : V_H \to \mathrm{Set}\ V_G$, such that: 1. For every vertex $v \in V_H$, the subgraph of $G$ induced by $X(v)$ is connected; 2. For all vertices $u, v \in V_H$, if $u \neq v$, then $X(u)$ and $X(v)$ are disjoint; 3. For all vertices $u, v \in V_H$, if $u \neq v$, then $u$ and $v$ are adjacent in $H$ if and only if there exist $x \in X(u)$ and $y \in X(v)$ such that $x$ and $y$ are adjacent in $G$.

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

/-- A graph H is an induced minor of G if there exist pairwise disjoint connected branch sets in G whose adjacencies in G reflect the adjacency of H. -/
def is_induced_minor {V_H V_G : Type*} (H : SimpleGraph V_H) (G : SimpleGraph V_G) : Prop := ∃ X : V_H → Set V_G,
    (∀ v, (G.induce (X v)).Connected) ∧
    (∀ u v, u ≠ v → Disjoint (X u) (X v)) ∧
    (∀ u v, u ≠ v → (H.Adj u v ↔ ∃ x ∈ X u, ∃ y ∈ X v, G.Adj x y))
See it in the graphDiscuss this resultChallenge it