Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Kuratowski's theorem: no K5K_5K5​ or K3,3K_{3,3}K3,3​ subdivision implies a plane drawing

Open
TenChallenges.kuratowski_isPlanar

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

kuratowskiplanar-graphsten-challengestopological-minor

Kuratowski's theorem (hard direction). Let GGG be a finite simple graph that contains no subdivision of K5K_5K5​ and no subdivision of K3,3K_{3,3}K3,3​. Then GGG is planar: it has a drawing in R2\mathbb R^2R2 in which vertices are distinct points, each edge is a simple arc between its ends avoiding all other vertices, and distinct edges meet only at common endpoints.

K5̸⪯topG  and  K3,3̸⪯topG⟹G is planar.K_5\not\preceq_{\mathrm{top}} G\ \text{ and }\ K_{3,3}\not\preceq_{\mathrm{top}} G\quad\Longrightarrow\quad G\ \text{is planar}.K5​⪯top​G  and  K3,3​⪯top​G⟹G is planar.

Together with the fact that topological minors are minors, it implies Wagner's theorem that graphs with no K5K_5K5​ or K3,3K_{3,3}K3,3​ minor are planar.

Formalization Note Containing a subdivision is SimpleGraph.TopologicalMinor; planarity is IsPlanar from Graph Minors V (a PlaneDrawing by simple arcs).

Preamble
import Definitions.Def_TenChallenges_Minor
import Definitions.Def_TenChallenges_TopologicalMinor
import Definitions.Def_RobertsonSeymour1986_GM5_IsPlanar
Formal statement
namespace TenChallenges
theorem kuratowski_isPlanar {V : Type} [Fintype V] (G : SimpleGraph V)
    (h5 : ¬ Nonempty (SimpleGraph.TopologicalMinor SimpleGraph.K5 G))
    (h33 : ¬ Nonempty (SimpleGraph.TopologicalMinor SimpleGraph.K33 G)) :
    RobertsonSeymour1986.GM5.IsPlanar G := by sorry
end TenChallenges
Source
K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271–283: a finite graph is planar if and only if it contains no subgraph homeomorphic to K_5 or K_{3,3}.

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