Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Plane graphs, faces, triangulations and planar graphs (Diestel §4.2, §4.4)

Definition
DiestelGraphTheory_PlaneGraph

by tiago duque marques · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryplanar-graphs

Plane 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 G=(V,E)G=(V,E)G=(V,E) of finite sets such that

  1. V⊆R2V\subseteq\mathbb R^2V⊆R2;
  2. every edge e∈Ee\in Ee∈E is an arc between two vertices;
  3. different edges have different sets of endpoints;
  4. the interior e˚\mathring ee˚ of an edge (the arc minus its endpoints) contains no vertex and no point of any other edge.

Two vertices x≠yx\ne yx=y are adjacent if some edge is an arc between them; this defines the abstract graph of GGG. Writing GGG also for the point set V∪⋃EV\cup\bigcup EV∪⋃E, the faces of GGG are the regions of R2∖G\mathbb R^2\setminus GR2∖G.

A face fff is bounded by a triangle if there are vertices a,b,ca,b,ca,b,c and edges eab,ebc,ecae_{ab},e_{bc},e_{ca}eab​,ebc​,eca​ of GGG, arcs between a,ba,ba,b, between b,cb,cb,c and between c,ac,ac,a, whose union is exactly the frontier of fff. GGG 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; ∣V∣|V|∣V∣, ∣E∣|E|∣E∣ and the number of faces are measured with Nat.card.

Definition code
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
Source
R. Diestel, Graph Theory, 6th ed., Springer GTM 173 (2025), https://diestel-graph-theory.com/basic.html (free preview of Ch. 4-5). Section 4.2, p. 96 (plane graph, faces), p. 100 (plane triangulation); Section 4.4, p. 106 (planar).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

This file builds on the previous one (plane =R×R=\mathbb{R}\times\mathbb{R}=R×R with product topology; "arc between xxx and yyy" means a finite union of non-degenerate closed straight segments that is the image of a topological embedding φ:[0,1]→R2\varphi:[0,1]\to\mathbb{R}^2φ:[0,1]→R2 with φ(0)=x\varphi(0)=xφ(0)=x, φ(1)=y\varphi(1)=yφ(1)=y, hence x≠yx\neq yx=y; "regions of OOO" means the sets Ra={b∈O:b=a or some arc between a,b lies in O}R_a=\{b\in O: b=a \text{ or some arc between } a,b \text{ lies in } O\}Ra​={b∈O:b=a or some arc between a,b lies in O} for a∈Oa\in Oa∈O).

Arc endpoints. For e⊆R2e\subseteq\mathbb{R}^2e⊆R2,

ends⁡(e)={ z:∃w, e is an arc between z and w or between w and z }.\operatorname{ends}(e)=\{\,z : \exists w,\ e \text{ is an arc between } z \text{ and } w \text{ or between } w \text{ and } z\,\}.ends(e)={z:∃w, e is an arc between z and w or between w and z}.

If eee is not an arc at all, ends⁡(e)=∅\operatorname{ends}(e)=\emptysetends(e)=∅. (For an arc between xxx and yyy this is the set of points that can serve as an end of some parametrisation; topologically these are just {x,y}\{x,y\}{x,y}, but the definition is stated via all parametrisations.)

Arc interior. e˚=e∖ends⁡(e)\mathring e = e\setminus\operatorname{ends}(e)e˚=e∖ends(e).

Plane graph. A plane graph HHH consists of a set V⊆R2V\subseteq\mathbb{R}^2V⊆R2 (vertices) and a set EEE of subsets of R2\mathbb{R}^2R2 (edges) such that:

  1. VVV is finite and EEE is finite;
  2. every e∈Ee\in Ee∈E is an arc between some x∈Vx\in Vx∈V and some y∈Vy\in Vy∈V (so x≠yx\ne yx=y);
  3. for e,e′∈Ee,e'\in Ee,e′∈E, if ends⁡(e)=ends⁡(e′)\operatorname{ends}(e)=\operatorname{ends}(e')ends(e)=ends(e′) then e=e′e=e'e=e′;
  4. for every e∈Ee\in Ee∈E, e˚∩V=∅\mathring e\cap V=\emptysete˚∩V=∅;
  5. for e≠e′e\neq e'e=e′ in EEE, e˚∩e′=∅\mathring e\cap e'=\emptysete˚∩e′=∅ (the interior of eee meets no point of e′e'e′, including the endpoints of e′e'e′).

V=∅V=\emptysetV=∅ (and then necessarily E=∅E=\emptysetE=∅) is allowed.

Point set. pts⁡(H)=V∪⋃e∈Ee\operatorname{pts}(H)=V\cup\bigcup_{e\in E}epts(H)=V∪⋃e∈E​e.

Abstract graph. abs⁡(H)\operatorname{abs}(H)abs(H) is the simple graph on the vertex type VVV in which distinct x,y∈Vx,y\in Vx,y∈V are adjacent iff some e∈Ee\in Ee∈E is an arc between xxx and yyy or an arc between yyy and xxx (symmetrised, loops removed).

Faces. faces⁡(H)=regions⁡(R2∖pts⁡(H))\operatorname{faces}(H)=\operatorname{regions}\bigl(\mathbb{R}^2\setminus\operatorname{pts}(H)\bigr)faces(H)=regions(R2∖pts(H)).

Bounded by a triangle. A set fff is bounded by a triangle of HHH if there exist a,b,c∈Va,b,c\in Va,b,c∈V and eab,ebc,eca∈Ee_{ab},e_{bc},e_{ca}\in Eeab​,ebc​,eca​∈E with eabe_{ab}eab​ an arc between a,ba,ba,b, ebce_{bc}ebc​ an arc between b,cb,cb,c, ecae_{ca}eca​ an arc between c,ac,ac,a, and

∂f=eab∪ebc∪eca,\partial f = e_{ab}\cup e_{bc}\cup e_{ca},∂f=eab​∪ebc​∪eca​,

where ∂f\partial f∂f is the topological frontier (closure minus interior) of fff in R2\mathbb{R}^2R2. Distinctness of a,b,ca,b,ca,b,c is not stated explicitly but follows from the arc conditions (a≠ba\ne ba=b, b≠cb\ne cb=c, c≠ac\ne ac=a).

Triangulation. HHH is a triangulation if every face of HHH is bounded by a triangle of HHH. (E.g. for V=E=∅V=E=\emptysetV=E=∅ the only face is R2\mathbb{R}^2R2, whose frontier is empty, so that graph is not a triangulation.)

Planar. A simple graph GGG on an arbitrary vertex type WWW is planar if there exists a plane graph HHH and a graph isomorphism G≅abs⁡(H)G\cong\operatorname{abs}(H)G≅abs(H) (a bijection W→VW\to VW→V preserving and reflecting adjacency). In particular a planar graph has finitely many vertices.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by tiago duque marques · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me