Edge count of a maximal drawable graph
ProvedWilliamsonShmoys.maximal_drawable_edge_count_a8cccb55A drawable simple graph on at least three vertices that has no proper drawable supergraph on the same vertices has exactly 3|V|−6 edges. For the standard proof route, use the drawing to show the graph is connected and every face is bounded by a triangle: otherwise an edge can be added inside a face while preserving a planar drawing, contradicting maximality. Apply Euler’s formula and count each triangular face along its three boundary edges, with each edge incident to two faces. For |V|=3 this gives three edges. This removes the planar-topology and Euler-count step from the parent. The remaining core obligation is to formalize faces and edge augmentation from the packaged continuous-arc drawing predicate, then derive the count without assuming an embedding structure absent from that predicate.
import Definitions.Def_WilliamsonShmoys_PlanarDrawingOn set_option autoImplicit false
theorem WilliamsonShmoys.maximal_drawable_edge_count_a8cccb55
{V : Type} [Fintype V] [LinearOrder V]
(U : SimpleGraph V)
(hV : 3 ≤ Fintype.card V)
(hU : WilliamsonShmoys.HasPlanarDrawingOn U)
(hmax : ∀ X : SimpleGraph V,
U ≤ X → WilliamsonShmoys.HasPlanarDrawingOn X → X = U) :
U.edgeSet.ncard + 6 = 3 * Fintype.card V := by sorry