A plane triangulation with vertices has edges (Diestel, Corollary 4.2.10)
OpenDiestelGraphTheory.triangulation_edgesLet be a plane triangulation, i.e. a plane graph each of whose faces, including the outer face, is bounded by a triangle of . If has vertices and edges, then
Together with the fact that maximal plane graphs are triangulations, this gives the edge bound for all plane graphs.
Formalization Note is natural-number subtraction; every plane triangulation has at least vertices (a graph with fewer has a face whose frontier is not a triangle), so it is exact.
import Mathlib import Definitions.Def_DiestelGraphTheory_PolygonalArc import Definitions.Def_DiestelGraphTheory_PlaneGraph
namespace DiestelGraphTheory
theorem triangulation_edges (G : PlaneGraph) (hG : G.IsTriangulation) :
Nat.card G.E = 3 * Nat.card G.V - 6 := by sorry
end DiestelGraphTheoryRead-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 , .
Assume is a triangulation: for every face of — a face being one of the distinct sets
— there are vertices and edges , where is an arc between and , between and , between and , such that the topological frontier of in is exactly
Then
with natural-number (truncated) subtraction: if the right side would be . (The hypothesis already forces : every face is bounded by three edges with pairwise distinct endpoints , and there is always at least one face since is a bounded set; so the truncation does not actually come into play.) No connectivity assumption is made explicitly.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.