Every non-empty plane graph has a vertex of degree at most
OpenDiestelGraphTheory.plane_exists_degree_le_fiveLet be a plane graph with at least one vertex. Then some vertex of satisfies
where is the number of neighbours of in the abstract graph of .
This is the step of the five colour proof that removes a vertex and applies induction; it is where Euler's formula enters the colouring argument.
import Mathlib import Definitions.Def_DiestelGraphTheory_PolygonalArc import Definitions.Def_DiestelGraphTheory_PlaneGraph
namespace DiestelGraphTheory
theorem plane_exists_degree_le_five (G : PlaneGraph) (hne : G.V.Nonempty) :
∃ v : G.V, Nat.card (G.toSimpleGraph.neighborSet v) ≤ 5 := 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 non-empty. Consider the abstract graph on in which distinct vertices are adjacent iff some is an arc between and (or between and ). Then there exists a vertex whose set of neighbours in this graph satisfies
( is a subset of the finite set , so its cardinality is a genuine finite count.) No connectivity is assumed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.