simple_graph_is_minor
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
- not_planar_all_powers_well_covered_characterizationIt is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is…
- cycle_seven_is_planarThe 7-cycle graph C_7 is planar.
- simple_graph_is_planarA simple graph G is planar by Wagner's criterion if neither the complete graph on 5 vertices nor the complete bipartite graph K_{3,3} is a…
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)