A plane graph with vertices has at most edges (Diestel, Corollary 4.2.10)
OpenDiestelGraphTheory.plane_edges_legraph-theoryplanar-graphs
Let be a plane graph with vertices and edges. Then
No connectedness is assumed. This bound is what forces every planar graph to have a vertex of degree at most , and it shows that is not planar.
Formalization Note Since , the natural-number subtraction is exact.
Preamble
import Mathlib import Definitions.Def_DiestelGraphTheory_PolygonalArc import Definitions.Def_DiestelGraphTheory_PlaneGraph
Formal statement
namespace DiestelGraphTheory
theorem plane_edges_le (G : PlaneGraph) (hn : 3 ≤ Nat.card G.V) :
Nat.card G.E ≤ 3 * Nat.card G.V - 6 := by sorry
end DiestelGraphTheorySource
R. Diestel, Graph Theory, 6th ed., Springer GTM 173 (2025), https://diestel-graph-theory.com/basic.html (free preview of Ch. 4-5). Corollary 4.2.10 (first assertion), p. 102.
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a plane graph: a finite set and a finite set of subsets of (plane = with product topology) such that
- each is an arc between some : a finite union of closed non-degenerate straight segments that is the image of a topological embedding with , (so );
- writing for the set of points such that is an arc between and some point or between some point and , distinct edges have distinct ;
- the interior of each edge contains no vertex, and for , .
No connectivity is assumed. Assume . Then
The subtraction is natural-number (truncated) subtraction, but under we have , so it agrees with ordinary subtraction.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.