6-colourability
Lax332265.SixColorable · concepts/Lax332265/SixColorable.lean · lax-332265
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A graph is 6-colourable when its vertices can be assigned six colours so that the endpoints of every edge receive different colours.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Combinatorics.SimpleGraph.Basic |
| 2 | import Mathlib.Data.Fin.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: 6-colourability |
| 7 | type: definition |
| 8 | --- |
| 9 | A graph is 6-colourable when its vertices can be assigned six colours so |
| 10 | that the endpoints of every edge receive different colours. |
| 11 | |
| 12 | # Formalization notes |
| 13 | |
| 14 | The six colours form the canonical type `Fin 6`, and a colouring is a plain |
| 15 | function from vertices to colours. Properness is expressed directly by |
| 16 | requiring adjacent vertices to have unequal images. This keeps the definition |
| 17 | independent of decidability assumptions and equivalent to the usual assertion |
| 18 | that the chromatic number is at most six, without introducing a separate |
| 19 | chromatic-number parameter that no statement in this submission needs. |
| 20 | |
| 21 | The definition applies to arbitrary vertex types because colourability is a |
| 22 | pointwise graph property. The conjecture itself is stated on the canonical |
| 23 | finite carriers `Fin n`. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax332265.SixColorable |
| 27 | |
| 28 | /-- A graph admits a proper vertex colouring with the six colours in `Fin 6`. -/ |
| 29 | def IsSixColorable {V : Type*} (G : SimpleGraph V) : Prop := |
| 30 | ∃ colour : V → Fin 6, |
| 31 | ∀ ⦃u v : V⦄, G.Adj u v → colour u ≠ colour v |
| 32 | |
| 33 | end Lax332265.SixColorable |
| 34 |
Formalization notes
The six colours form the canonical type , and a colouring is a plain function from vertices to colours. Properness is expressed directly by requiring adjacent vertices to have unequal images. This keeps the definition independent of decidability assumptions and equivalent to the usual assertion that the chromatic number is at most six, without introducing a separate chromatic-number parameter that no statement in this submission needs.
The definition applies to arbitrary vertex types because colourability is a pointwise graph property. The conjecture itself is stated on the canonical finite carriers .
Builds on
none
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments