AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_minor

def

A graph H is a minor of a graph G if there exists a family of pairwise disjoint, non-empty, connected subsets B_u of V(G) indexed by u in V(H) such that whenever u and v are adjacent in H, there is an edge in G between B_u and B_v.

Statement

def simple_graph_is_minor {U V : Type*} (H : SimpleGraph U) (G : SimpleGraph V) : Prop
Defined in
Diestel, Graph Theory (5th ed.), Section 1.7
Verified
26 Oct 2026
Axioms
none listed
Used by 3

Read back from the Lean

Given types $U$ and $V$, a simple graph $H$ on vertex type $U$, and a simple graph $G$ on vertex type $V$, the proposition simple_graph_is_minor H G asserts that there exists a function $B : U \to \mathrm{Set}\;V$ (assigning to each vertex of $U$ a subset of $V$, called a branch set) such that: 1. For every $u : U$, the induced subgraph of $G$ on $B(u)$ is connected ((G.induce (B u)).Connected). 2. For every $u, v : U$, if $u \ne v$, then $B(u)$ and $B(v)$ are disjoint (Disjoint (B u) (B v)). 3. For every $u, v : U$, if $u$ is adjacent to $v$ in $H$ (H.Adj u v), then there exist vertices $x \in B(u)$ and $y \in B(v)$ such that $x$ is adjacent to $y$ in $G$ (G.Adj x y).

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

/-- H is a graph minor of G if there exist pairwise disjoint connected branch sets in G adjacent whenever H is. -/
def simple_graph_is_minor {U V : Type*} (H : SimpleGraph U) (G : SimpleGraph V) : Prop := ∃ B : U → Set V,
    (∀ u, (G.induce (B u)).Connected) ∧
    (∀ u v, u ≠ v → Disjoint (B u) (B v)) ∧
    (∀ u v, H.Adj u v → ∃ x ∈ B u, ∃ y ∈ B v, G.Adj x y)
See it in the graphDiscuss this resultChallenge it