Plane graphs, faces, triangulations and planar graphs (Diestel §4.2, §4.4)
DefinitionDiestelGraphTheory_PlaneGraphPlane and planar graphs, following Diestel, Sections 4.2 and 4.4. Arcs, polygons and regions are as in DiestelGraphTheory_PolygonalArc.
A plane graph is a pair of finite sets such that
- ;
- every edge is an arc between two vertices;
- different edges have different sets of endpoints;
- the interior of an edge (the arc minus its endpoints) contains no vertex and no point of any other edge.
Two vertices are adjacent if some edge is an arc between them; this defines the abstract graph of . Writing also for the point set , the faces of are the regions of .
A face is bounded by a triangle if there are vertices and edges of , arcs between , between and between , whose union is exactly the frontier of . is a plane triangulation if every face (including the outer face) is bounded by a triangle.
An abstract graph is planar if it is isomorphic to the abstract graph of some plane graph.
These are the objects of Euler's formula and of the Four and Five Colour Theorems.
Formalization Note The abstract graph is built with SimpleGraph.fromRel on the vertex set; , and the number of faces are measured with Nat.card.
import Mathlib
import Definitions.Def_DiestelGraphTheory_PolygonalArc
/-!
Plane graphs, their faces, plane triangulations, and planar graphs, following
R. Diestel, *Graph Theory*, 6th ed. (Springer GTM 173, 2025), Sections 4.2 and 4.4.
-/
namespace DiestelGraphTheory
open Set
/-- The *endpoints* of an arc `e`: the points `z` such that `e` is an arc between
`z` and some point, or between some point and `z`. -/
def arcEnds (e : Set (ℝ × ℝ)) : Set (ℝ × ℝ) :=
{z : ℝ × ℝ | ∃ w : ℝ × ℝ, IsArcBetween e z w ∨ IsArcBetween e w z}
/-- The *interior* `e̊ = e \ {x, y}` of an arc `e` between `x` and `y`. -/
def arcInterior (e : Set (ℝ × ℝ)) : Set (ℝ × ℝ) := e \ arcEnds e
/-- A *plane graph* `(V, E)` (Diestel, §4.2): finite sets `V ⊆ ℝ²` of vertices and
`E` of edges such that
1. every edge is an arc between two vertices;
2. different edges have different sets of endpoints;
3. the interior of an edge contains no vertex and no point of any other edge. -/
structure PlaneGraph where
/-- The vertices: points of the plane. -/
V : Set (ℝ × ℝ)
/-- The edges: subsets of the plane. -/
E : Set (Set (ℝ × ℝ))
V_finite : V.Finite
E_finite : E.Finite
edge_isArc : ∀ e ∈ E, ∃ x ∈ V, ∃ y ∈ V, IsArcBetween e x y
ends_injective : ∀ e ∈ E, ∀ e' ∈ E, arcEnds e = arcEnds e' → e = e'
interior_disjoint_vertices : ∀ e ∈ E, Disjoint (arcInterior e) V
interior_disjoint_edges : ∀ e ∈ E, ∀ e' ∈ E, e ≠ e' → Disjoint (arcInterior e) e'
namespace PlaneGraph
/-- The point set `V ∪ ⋃ E` of a plane graph. -/
def pointSet (H : PlaneGraph) : Set (ℝ × ℝ) := H.V ∪ ⋃₀ H.E
/-- The abstract graph defined by a plane graph: two distinct vertices `x, y` are
adjacent iff some edge is an arc between them. -/
def toSimpleGraph (H : PlaneGraph) : SimpleGraph H.V :=
SimpleGraph.fromRel fun x y => ∃ e ∈ H.E, IsArcBetween e (x : ℝ × ℝ) (y : ℝ × ℝ)
/-- The *faces* of a plane graph `G`: the regions of `ℝ² \ G` (Diestel, §4.2). -/
def faces (H : PlaneGraph) : Set (Set (ℝ × ℝ)) := regions (H.pointSet)ᶜ
/-- A face `f` is *bounded by a triangle* of `H`: there are three vertices `a, b, c`
and edges `e_ab, e_bc, e_ca` of `H` (arcs between `a,b`, `b,c`, `c,a`) whose union
is exactly the frontier of `f`. -/
def IsBoundedByTriangle (H : PlaneGraph) (f : Set (ℝ × ℝ)) : Prop :=
∃ a ∈ H.V, ∃ b ∈ H.V, ∃ c ∈ H.V,
∃ eab ∈ H.E, ∃ ebc ∈ H.E, ∃ eca ∈ H.E,
IsArcBetween eab a b ∧ IsArcBetween ebc b c ∧ IsArcBetween eca c a ∧
frontier f = eab ∪ ebc ∪ eca
/-- A *plane triangulation*: every face (including the outer face) is bounded by a
triangle (Diestel, §4.2). -/
def IsTriangulation (H : PlaneGraph) : Prop :=
∀ f ∈ H.faces, H.IsBoundedByTriangle f
end PlaneGraph
/-- A graph is *planar* if it is isomorphic to (the abstract graph of) a plane graph
(Diestel, §4.4). -/
def IsPlanar {V : Type*} (G : SimpleGraph V) : Prop :=
∃ H : PlaneGraph, Nonempty (G ≃g H.toSimpleGraph)
end DiestelGraphTheory
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This file builds on the previous one (plane with product topology; "arc between and " means a finite union of non-degenerate closed straight segments that is the image of a topological embedding with , , hence ; "regions of " means the sets for ).
Arc endpoints. For ,
If is not an arc at all, . (For an arc between and this is the set of points that can serve as an end of some parametrisation; topologically these are just , but the definition is stated via all parametrisations.)
Arc interior. .
Plane graph. A plane graph consists of a set (vertices) and a set of subsets of (edges) such that:
- is finite and is finite;
- every is an arc between some and some (so );
- for , if then ;
- for every , ;
- for in , (the interior of meets no point of , including the endpoints of ).
(and then necessarily ) is allowed.
Point set. .
Abstract graph. is the simple graph on the vertex type in which distinct are adjacent iff some is an arc between and or an arc between and (symmetrised, loops removed).
Faces. .
Bounded by a triangle. A set is bounded by a triangle of if there exist and with an arc between , an arc between , an arc between , and
where is the topological frontier (closure minus interior) of in . Distinctness of is not stated explicitly but follows from the arc conditions (, , ).
Triangulation. is a triangulation if every face of is bounded by a triangle of . (E.g. for the only face is , whose frontier is empty, so that graph is not a triangulation.)
Planar. A simple graph on an arbitrary vertex type is planar if there exists a plane graph and a graph isomorphism (a bijection preserving and reflecting adjacency). In particular a planar graph has finitely many vertices.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.