Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Topological minor (subdivision) of a simple graph

Definition
TenChallenges_TopologicalMinor

by Davide · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-minorsten-challengestopological-minor

A graph GGG contains a subdivision of a graph HHH (equivalently, HHH is a topological minor of GGG) if there are

  • an injective map v↦φ(v)v\mapsto \varphi(v)v↦φ(v) from the vertices of HHH to vertices of GGG (the branch vertices), and
  • for every edge ababab of HHH a path PabP_{ab}Pab​ in GGG from φ(a)\varphi(a)φ(a) to φ(b)\varphi(b)φ(b),

such that no path PabP_{ab}Pab​ passes through a branch vertex other than φ(a)\varphi(a)φ(a) and φ(b)\varphi(b)φ(b), and paths belonging to distinct edges of HHH meet only in branch vertices. Equivalently, GGG has a subgraph obtained from HHH by replacing its edges with internally disjoint paths. This is the containment relation of Kuratowski's theorem.

Formalization Note The structure stores a path for each ordered adjacency H.Adj a b; the paths for (a,b) and (b,a) are not required to agree, since they belong to the same edge s(a,b)s(a,b)s(a,b) and the disjointness condition is only imposed for distinct edges. Any such data yields a subdivision by keeping one path per edge.

Definition code
import Mathlib.Combinatorics.SimpleGraph.Paths

namespace SimpleGraph

variable {W V : Type*}

/-- The data witnessing that `G` contains a subdivision of `H` (a *topological minor*):
an injective map sending the vertices of `H` to *branch vertices* of `G`, and for every edge
`ab` of `H` a path of `G` from the branch vertex of `a` to that of `b`, such that a path meets
no branch vertex other than its two ends, and paths of distinct edges of `H` share only
branch vertices. -/
structure TopologicalMinor (H : SimpleGraph W) (G : SimpleGraph V) where
  /-- The branch vertex of each vertex of `H`. -/
  vertexMap : W ↪ V
  /-- The subdivided edge: a path between the branch vertices of the ends. -/
  path : ∀ ⦃a b : W⦄, H.Adj a b → G.Walk (vertexMap a) (vertexMap b)
  /-- Each subdivided edge is a path. -/
  path_isPath : ∀ ⦃a b : W⦄ (h : H.Adj a b), (path h).IsPath
  /-- A subdivided edge meets no branch vertex except its two ends. -/
  path_branch : ∀ ⦃a b : W⦄ (h : H.Adj a b) (x : W),
    vertexMap x ∈ (path h).support → x = a ∨ x = b
  /-- Subdivided edges of distinct edges of `H` meet only in branch vertices. -/
  path_disjoint : ∀ ⦃a b c d : W⦄ (h : H.Adj a b) (k : H.Adj c d), s(a, b) ≠ s(c, d) →
    ∀ v, v ∈ (path h).support → v ∈ (path k).support → ∃ x, vertexMap x = v

end SimpleGraph
Source
Standard notion; Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271–283 ('subgraph homeomorphic to K_5 or K_{3,3}'); see e.g. Diestel, Graph Theory, Sect. 1.7 (topological minors).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me