6-colourability

Lax332265.SixColorable · concepts/Lax332265/SixColorable.lean · lax-332265

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    1 concept; 1 descendant hidden
    100%
    Open claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Basic
    2import Mathlib.Data.Fin.Basic
    3
    4/-!
    5---
    6title: 6-colourability
    7type: definition
    8---
    9A graph is 6-colourable when its vertices can be assigned six colours so
    10that the endpoints of every edge receive different colours.
    11
    12# Formalization notes
    13
    14The six colours form the canonical type `Fin 6`, and a colouring is a plain
    15function from vertices to colours. Properness is expressed directly by
    16requiring adjacent vertices to have unequal images. This keeps the definition
    17independent of decidability assumptions and equivalent to the usual assertion
    18that the chromatic number is at most six, without introducing a separate
    19chromatic-number parameter that no statement in this submission needs.
    20
    21The definition applies to arbitrary vertex types because colourability is a
    22pointwise graph property. The conjecture itself is stated on the canonical
    23finite carriers `Fin n`.
    24-/
    25
    26namespace Lax332265.SixColorable
    27
    28/-- A graph admits a proper vertex colouring with the six colours in `Fin 6`. -/
    29def 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
    33end Lax332265.SixColorable
    34
    Formalization notes

    The six colours form the canonical type Fin6Fin 6, 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 FinnFin n.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…