Polygonal arcs, polygons and regions in (Diestel §4.1)
DefinitionDiestelGraphTheory_PolygonalArcTopological prerequisites for plane graphs, following Diestel, Section 4.1. The plane carries its Euclidean topology, and every subset carries the subspace topology.
- A straight line segment is a set for two distinct points of .
- A polygon is a subset of that is the union of finitely many straight line segments and is homeomorphic to the unit circle .
- A (polygonal) arc between and is a subset that is the union of finitely many straight line segments and admits a homeomorphism with and ; the points are its endpoints.
- For , two points are linked by an arc in if or some arc between and is contained in .
- The regions of are the classes for . For open (the only case used) these are the equivalence classes of the linking relation.
These notions underlie the definition of plane graphs and their faces, and the Jordan Curve Theorem for polygons.
Formalization Note is ℝ × ℝ, whose product topology is the Euclidean one; because Mathlib's metric on ℝ × ℝ is the sup metric, the unit circle is written by its Euclidean equation. A homeomorphism is encoded as a topological embedding of unitInterval with range .
import Mathlib
/-!
Topological prerequisites for plane graphs, following
R. Diestel, *Graph Theory*, 6th ed. (Springer GTM 173, 2025), Section 4.1.
The Euclidean plane `ℝ²` is modelled as `ℝ × ℝ` with its product topology
(which is the Euclidean topology). Every subset carries the subspace topology.
-/
namespace DiestelGraphTheory
open Set
/-- A *straight line segment*: a set of the form `{p + λ (q - p) | 0 ≤ λ ≤ 1}`
for two distinct points `p ≠ q` of the plane (Diestel, §4.1). -/
def IsStraightSegment (S : Set (ℝ × ℝ)) : Prop :=
∃ p q : ℝ × ℝ, p ≠ q ∧
S = {z : ℝ × ℝ | ∃ t : ℝ, 0 ≤ t ∧ t ≤ 1 ∧ z = p + t • (q - p)}
/-- `P` is the union of finitely many straight line segments. -/
def IsFiniteUnionOfSegments (P : Set (ℝ × ℝ)) : Prop :=
∃ (k : ℕ) (S : Fin k → Set (ℝ × ℝ)), (∀ i, IsStraightSegment (S i)) ∧ P = ⋃ i, S i
/-- The unit circle `S¹ = {z ∈ ℝ² | ‖z‖₂ = 1}` (Euclidean norm, not the sup norm
that `ℝ × ℝ` carries in Mathlib). -/
def unitCircle : Set (ℝ × ℝ) := {z : ℝ × ℝ | z.1 ^ 2 + z.2 ^ 2 = 1}
/-- A *polygon*: a finite union of straight line segments homeomorphic to the
unit circle `S¹` (Diestel, §4.1). -/
def IsPolygon (P : Set (ℝ × ℝ)) : Prop :=
IsFiniteUnionOfSegments P ∧ Nonempty (P ≃ₜ unitCircle)
/-- `P` is a *(polygonal) arc between `x` and `y`*: a finite union of straight line
segments that is homeomorphic to `[0,1]` via a homeomorphism sending `0 ↦ x` and
`1 ↦ y` (Diestel, §4.1). A topological embedding `[0,1] → ℝ²` with range `P` is
exactly a homeomorphism `[0,1] ≅ P`. -/
def IsArcBetween (P : Set (ℝ × ℝ)) (x y : ℝ × ℝ) : Prop :=
IsFiniteUnionOfSegments P ∧
∃ φ : unitInterval → ℝ × ℝ,
Topology.IsEmbedding φ ∧ range φ = P ∧ φ 0 = x ∧ φ 1 = y
/-- Two points `a, b` of an open set `O` are *linked by an arc in `O`*: they are
equal, or some arc between `a` and `b` lies inside `O` (Diestel, §4.1). -/
def LinkedIn (O : Set (ℝ × ℝ)) (a b : ℝ × ℝ) : Prop :=
a = b ∨ ∃ P : Set (ℝ × ℝ), IsArcBetween P a b ∧ P ⊆ O
/-- The *regions* of `O ⊆ ℝ²`: the equivalence classes of points of `O` under
"being linked by an arc in `O`" (Diestel, §4.1). -/
def regions (O : Set (ℝ × ℝ)) : Set (Set (ℝ × ℝ)) :=
{R | ∃ a ∈ O, R = {b : ℝ × ℝ | b ∈ O ∧ LinkedIn O a b}}
end DiestelGraphTheory
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This file introduces six notions about subsets of the plane, where the plane is with the product topology (which coincides with the Euclidean topology; Mathlib's default metric on the product is the sup metric, but only the topology and the vector operations are used here). Every subset carries the subspace topology.
Straight segment. A set is a straight segment if there are points with
i.e. a closed, non-degenerate line segment (a single point is excluded).
Finite union of segments. is a finite union of segments if there exist and straight segments with . Here is allowed, so the empty set qualifies.
Unit circle. (Euclidean circle, written by its equation, not the unit sphere of the sup norm), with the subspace topology.
Polygon. is a polygon if it is a finite union of segments and there exists a homeomorphism (both with subspace topologies).
Arc between and . is an arc between and if is a finite union of segments and there is a map that is a topological embedding (continuous, injective, and a homeomorphism onto its image), with image exactly , and . Since is injective, this forces ; is non-empty and compact. The order matters only formally (reversing shows "arc between " is equivalent to "arc between ").
Linked in . For and points : and are linked in if either (with no requirement that ), or there is a set that is an arc between and with .
Regions. For , the regions of form the set of subsets
It is a set of sets, so base points giving the same yield one element. No openness of is required by the definition, and the definition itself does not assert that "linked in " is an equivalence relation (for arbitrary the sets need not partition ). If there are no regions.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.