Euler's formula (Diestel, Theorem 4.2.9)
OpenDiestelGraphTheory.euler_formulaLet be a connected plane graph with vertices, edges and faces (regions of ). Then
Euler's formula is the basic counting identity for plane graphs; it yields the edge bound and hence the existence of a vertex of degree at most .
Formalization Note Connectedness is that of the abstract graph and, as in Diestel, includes non-emptiness. The identity is stated in ; is Nat.card of the set of faces, so the statement also asserts that there are finitely many faces.
import Mathlib import Definitions.Def_DiestelGraphTheory_PolygonalArc import Definitions.Def_DiestelGraphTheory_PlaneGraph
namespace DiestelGraphTheory
theorem euler_formula (G : PlaneGraph) (hG : G.toSimpleGraph.Connected) :
(Nat.card G.V : ℤ) - Nat.card G.E + Nat.card G.faces = 2 := 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 the abstract graph of is connected: on vertex set , distinct are adjacent iff some edge is an arc between them; connectedness (Mathlib's notion) requires to be non-empty and any two vertices to be joined by a walk.
Let the faces of be the regions of , i.e. the distinct sets
Then, computed in the integers,
where , are the (finite) cardinalities and is the cardinality of the set of faces, with the convention that this cardinality is if the set of faces were infinite.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.