is_induced_minor_induce
If 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.
Statement
theorem is_induced_minor_induce {V_H V_G : Type*} (H : SimpleGraph V_H) (G : SimpleGraph V_G) (h_minor : is_induced_minor H G) (A : Set V_H) : is_induced_minor (H.induce A) G
- Source
- arXiv:2611.09627 Section 2
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_induced_minorA 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…
Read back from the Lean
For any types V_H and V_G, simple graphs H on V_H and G on V_G, if H is an induced minor of G (is_induced_minor H G), then for every subset A of V_H, the induced subgraph of H on A (H.induce A) is also an induced minor of G.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the induced subgraph $H[A]$ is an induced minor of $G$, we restrict the branch sets witnessing that $H$ is an induced minor of $G$ to vertices belonging to $A$. Connectivity of the branch sets is inherited immediately, distinct vertices in $A$ remain distinct in $H$ ensuring disjointness, and the definition of an induced subgraph ensures the edge correspondence is preserved.
There exists a family of branch sets witnessing that $H$ is an induced minor of $G$.
By definition of an induced minor, we obtain a family of branch sets $X(v) \subseteq V_G$ for each vertex $v \in V_H$ such that each $G[X(v)]$ is connected, branch sets of distinct vertices are pairwise disjoint, and vertices $u \neq v$ are adjacent in $H$ if and only if there is an edge between $X(u)$ and $X(v)$ in $G$.
rcases h_minor with ⟨X, hconn, hdisj, hadj⟩
Restricting the branch sets to the subset $A$ provides candidate branch sets whose induced subgraphs in $G$ are connected.
We associate to each vertex $v \in A$ the branch set $X(v)$ of its underlying vertex in $V_H$. Because each $G[X(v)]$ is already known to be connected, the connectivity requirement is satisfied immediately, leaving only disjointness and adjacency to verify.
refine ⟨fun v => X v.1, fun v => hconn v.1, ?_, ?_⟩
The restricted branch sets for distinct vertices in $A$ are pairwise disjoint.
For any distinct vertices $u \neq v$ in $A$, their underlying vertices in $V_H$ are also distinct by the injectivity of the inclusion of a subtype (`Subtype.val_injective.ne`). Hence, their branch sets are disjoint by the pairwise disjointness of the original family.
uses
Subtype.val_injective.ne· intro u v hne exact hdisj u.1 v.1 (Subtype.val_injective.ne hne)
Adjacency between distinct vertices in $H[A]$ corresponds to the existence of an edge between their branch sets in $G$.
By `SimpleGraph.induce_adj`, two vertices $u \neq v$ in $A$ are adjacent in $H[A]$ if and only if their underlying vertices are adjacent in $H$. Since $u \neq v$ implies their underlying vertices in $V_H$ are distinct (again by `Subtype.val_injective.ne`), the original adjacency equivalence applies directly.
uses
SimpleGraph.induce_adj,Subtype.val_injective.ne· intro u v hne rw [SimpleGraph.induce_adj] exact hadj u.1 v.1 (Subtype.val_injective.ne hne)
SimpleGraph.induce_adj- Two vertices in an induced subgraph are adjacent if and only if their underlying vertices are adjacent in the ambient graph.
Subtype.val_injective.ne- If two elements of a subtype are distinct, their underlying values are distinct.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- If H is an induced minor of G, then any induced subgraph of H is also an induced minor of G. -/theorem is_induced_minor_induce {V_H V_G : Type*} (H : SimpleGraph V_H) (G : SimpleGraph V_G) (h_minor : is_induced_minor H G) (A : Set V_H) : is_induced_minor (H.induce A) G := by rcases h_minor with ⟨X, hconn, hdisj, hadj⟩ refine ⟨fun v => X v.1, fun v => hconn v.1, ?_, ?_⟩ · intro u v hne exact hdisj u.1 v.1 (Subtype.val_injective.ne hne) · intro u v hne rw [SimpleGraph.induce_adj] exact hadj u.1 v.1 (Subtype.val_injective.ne hne)