Euler and face incidence equations for a maximal planar drawing
ProvedWilliamsonShmoys.maximal_planar_drawing_euler_face_incidence__p2m_4ca6b67e_a5cb_47ee_9958_b87be2ab6440_a1For a drawable simple graph on at least three vertices that is maximal among drawable supergraphs on the same vertex set, there is a natural number f, the number of faces, satisfying Euler’s equation |V| + f = |E| + 2 and the triangular face-edge incidence equation 3f = 2|E|. The three-vertex case is included; its embedding has two triangular faces. The first equation formalizes Euler’s characteristic for the plane map extracted from the drawing. The second follows by showing that maximality forces every face boundary to be a triangle. A proof route is to derive cyclic orders at vertices from the arcs, construct the facial boundary walks, prove Euler’s formula for the resulting finite plane map, and use maximality to exclude any face boundary with more than three edges. Together these equations reduce the target to arithmetic.
import Definitions.Def_WilliamsonShmoys_PlanarDrawingOn import Mathlib set_option autoImplicit false
theorem WilliamsonShmoys.maximal_planar_drawing_euler_face_incidence__p2m_4ca6b67e_a5cb_47ee_9958_b87be2ab6440_a1
{V : Type} [Fintype V] [LinearOrder V]
(H : SimpleGraph V) (dH : DecidableRel H.Adj)
(hH : WilliamsonShmoys.HasPlanarDrawingOn H)
(hcard : 3 ≤ Fintype.card V)
(hmax : ∀ (K : SimpleGraph V) (dK : DecidableRel K.Adj),
WilliamsonShmoys.HasPlanarDrawingOn K →
H.edgeFinset ⊆ K.edgeFinset →
K.edgeFinset ⊆ H.edgeFinset) :
∃ f : ℕ,
Fintype.card V + f = H.edgeFinset.card + 2 ∧
3 * f = 2 * H.edgeFinset.card := by sorry