Extend a nontrivial planar graph to a connected planar supergraph
ProvedWilliamsonShmoys.planar_connected_supergraph_exists__p2m_10f04ae6_54c9_4ed6_b5cd_b1cd1816504e_a1Any graph on at least three vertices with a crossing-free drawing has a connected supergraph on the same vertices that also has a crossing-free drawing. This strengthens the target’s strict-extension conclusion and isolates the geometric task of connecting components while preserving a drawing. The cardinality hypothesis rules out the empty-vertex boundary case flagged in earlier related work. A proof route is to normalize a finite planar embedding, then add noncrossing edges through faces until the components are connected, checking the arc and intersection requirements of HasPlanarDrawingOn. The remaining core obligation is to formalize that normalization and edge-insertion construction for the explicit arc-based definition; no existing proof source for that exact construction was verified.
import Definitions.Def_WilliamsonShmoys_PlanarDrawingOn import Mathlib open WilliamsonShmoys set_option autoImplicit false
theorem WilliamsonShmoys.planar_connected_supergraph_exists__p2m_10f04ae6_54c9_4ed6_b5cd_b1cd1816504e_a1
{V : Type} [Fintype V] [LinearOrder V]
(H : SimpleGraph V)
(hH : WilliamsonShmoys.HasPlanarDrawingOn H)
(hcard : 3 ≤ Fintype.card V) :
∃ K : SimpleGraph V,
H ≤ K ∧ K.Connected ∧ WilliamsonShmoys.HasPlanarDrawingOn K := by sorry