AFTD Auto-Formalizing Theoretical Domains

is_induced_minor_induce

theoremverified

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.

  1. 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$.

    line 5

      rcases h_minor with ⟨X, hconn, hdisj, hadj⟩
  2. 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.

    line 6

      refine ⟨fun v => X v.1, fun v => hconn v.1, ?_, ?_⟩
  3. 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.

    lines 7–8

    uses Subtype.val_injective.ne

      · intro u v hne
        exact hdisj u.1 v.1 (Subtype.val_injective.ne hne)
  4. 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.

    lines 9–11

    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

/-- 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)
See it in the graphDiscuss this resultChallenge it