Wagner's theorem: no or minor implies a plane drawing
OpenTenChallenges.wagner_isPlanarWagner's theorem (hard direction). Let be a finite simple graph that has neither the complete graph nor the complete bipartite graph as a minor. Then is planar: it has a drawing in the plane in which the vertices are distinct points, every edge is a simple arc joining its ends and avoiding all other vertices, and two distinct edges meet only at common endpoints.
This is the nontrivial half of Wagner's characterisation of planar graphs by excluded minors, the minor version of Kuratowski's theorem. It connects the combinatorial planarity notion used in the Ten Challenges 06 statement (Wagner's criterion) with the topological notion used in Graph Minors V.
Formalization Note The hypothesis is IsWagnerPlanar (no and no minor, branch-set model). The conclusion is IsPlanar from Graph Minors V: a PlaneDrawing by simple arcs.
import Definitions.Def_TenChallenges_Minor import Definitions.Def_RobertsonSeymour1986_GM5_IsPlanar
namespace TenChallenges
theorem wagner_isPlanar {V : Type} [Fintype V] (G : SimpleGraph V) (hG : G.IsWagnerPlanar) :
RobertsonSeymour1986.GM5.IsPlanar G := by sorry
end TenChallenges