Lagmental Vicfred

The Five-Color Theorem Uses a Low-Degree Vertex by Vicfred

tags: mathematics, planar graphs, coloring, duality

Euler's bound guarantees a vertex of degree at most five, enabling induction and a Kempe-chain recoloring. I want the notation, the mechanism, and the failure mode visible at the same time.

Notation

A planar embedding divides the sphere into vertices, edges, and faces. Euler's relation \(|V|-|E|+|F|=2\) constrains density, while the dual \(G^\ast\) records adjacency of faces.

$$ G\ \text{planar}\Longrightarrow\delta(G)\le5 $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ \chi(G)\le5 $$

Stress the formula

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ \frac1{|V|}\sum_{v\in V}\deg(v)=\frac{2|E|}{|V|}<6\Longrightarrow\exists v,\ \deg(v)\le5 $$

Interpretation

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad G\ \text{planar}\Longrightarrow\delta(G)\le5,\\[5pt] \mathsf{C}\;&:\quad \chi(G)\le5. \end{aligned} $$

Limit of the argument

Planarity is a property of a graph, while a plane graph includes a chosen embedding. The dual depends on that embedding.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \chi(G)\le5 \end{gathered}} $$

A symbolic summary is trustworthy only because the example and limitation remain visible beside it. The box compresses the conclusion without hiding its origin.

This article was posted on Thu 14 April 2011. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.