Topological minor (subdivision) of a simple graph
DefinitionTenChallenges_TopologicalMinorgraph-minorsten-challengestopological-minor
A graph contains a subdivision of a graph (equivalently, is a topological minor of ) if there are
- an injective map from the vertices of to vertices of (the branch vertices), and
- for every edge of a path in from to ,
such that no path passes through a branch vertex other than and , and paths belonging to distinct edges of meet only in branch vertices. Equivalently, has a subgraph obtained from 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 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).