Kuratowski's theorem: no or subdivision implies a plane drawing
OpenTenChallenges.kuratowski_isPlanarkuratowskiplanar-graphsten-challengestopological-minor
Kuratowski's theorem (hard direction). Let be a finite simple graph that contains no subdivision of and no subdivision of . Then is planar: it has a drawing in 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.
Together with the fact that topological minors are minors, it implies Wagner's theorem that graphs with no or 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 TenChallengesSource
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}.