is_induced_minor
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))