(6.4), p. 25 β every non-empty consistent set of edge-colourings of a 5-ring that meets β° includes one of πβ,β¦,πβ , πβ,β¦,πβ , β°
ProvedFourColourRSST.Ring.birkhoff_ring5Let be a circuit of length 5 with edges in order. For let be the equivalence class of the edge-colouring with , and for . For let
where are the two edges with a common end with ; and let
where are the edges different from , in order. Finally let .
Theorem (Birkhoff). Every non-empty consistent set of edge-colourings of with satisfies
This is Birkhoff's lemma for rings of length 5. In the RSST quadratic colouring algorithm (6.5) it is what allows a 4-colouring to be carried across a separating 5-circuit in the short-circuit subroutine. It is one ingredient of the proof of the Four-Colour Theorem, not the theorem itself.
Formalization Note. The circuit is cycleGraph 5 on Fin 5; the paper's is edge (0-based). Thus is A (i-1) (j-1), = A 0 1 βͺ A 1 2 βͺ A 2 3 βͺ A 3 4 βͺ A 0 4, the paper's is C5 (i-1) (built from edges , modulo 5, the two neighbours of edge ), and the paper's is D5 (i-1) with the four other edges read along the path starting next to . "Includes" is set inclusion and "meets" is non-empty intersection. The hypothesis that is non-empty is implied by meeting ; it is kept because the statement says it.
import Mathlib import Definitions.Def_FourColourRSST_Ring_Setting
namespace FourColourRSST.Ring
theorem birkhoff_ring5 (C : Set (EdgeColouring 5)) (hC : Consistent C)
(hne : C.Nonempty) (hmeet : (C β© E5).Nonempty) :
(β i, C5 i β C) β¨ (β i, D5 i β C) β¨ E5 β C := by sorry
end FourColourRSST.Ring
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.