While this submission is a draft, it cannot be used by other submissions.

Colored graphs

Lax119563.ColoredGraphs · concepts/Lax119563/ColoredGraphs.lean · lax-119563

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 colored graph G=(V(G),E(G),χG)G = (V(G), E(G), \chi_G) consists of a finite vertex set V(G)V(G), an edge set E(G)⊆(V(G)2)E(G) \subseteq \binom{V(G)}{2}, and a vertex coloring χG ⁣:V(G)→K\chi_G \colon V(G) \to \mathcal{K}. All graphs are simple and undirected, and every vertex has exactly one color.

    We take V(G)={0,…,n−1}V(G) = \{0, \dots, n-1\} for the number nn of vertices of GG, and use the natural numbers as the set of colors K\mathcal{K}. Thus any two colored graphs use the same set of colors and can be compared.

    Concept map
    1 concept
    100%
    DefinitionThis conceptDescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Basic
    2import Mathlib.SetTheory.Cardinal.Finite
    3
    4/-!
    5---
    6title: Colored graphs
    7type: definition
    8---
    9A *colored graph* G=(V(G),E(G),χG)G = (V(G), E(G), \chi_G) consists of a finite vertex set V(G)V(G),
    10an edge set E(G)⊆(V(G)2)E(G) \subseteq \binom{V(G)}{2}, and a vertex coloring
    11χG ⁣:V(G)→K\chi_G \colon V(G) \to \mathcal{K}. All graphs are simple and undirected, and every
    12vertex has exactly one color.
    13
    14We take V(G)={0,…,n−1}V(G) = \{0, \dots, n-1\} for the number nn of vertices of GG, and use the
    15natural numbers as the set of colors K\mathcal{K}. Thus any two colored graphs use the
    16same set of colors and can be compared.
    17-/
    18
    19namespace Lax119563.ColoredGraphs
    20
    21/-- A *colored graph* on the vertex set `{0, …, n-1}`, with colors in `ℕ`. -/
    22structure ColoredGraph where
    23 /-- The number of vertices. -/
    24 n : ℕ
    25 /-- The underlying simple graph; `graph.Adj p q` means that `pq` is an edge. -/
    26 graph : SimpleGraph (Fin n)
    27 /-- The vertex coloring. -/
    28 color : Fin n → ℕ
    29
    30/-- The number of edges of a colored graph. -/
    31noncomputable def ColoredGraph.numEdges (G : ColoredGraph) : ℕ :=
    32 Nat.card G.graph.edgeSet
    33
    34end Lax119563.ColoredGraphs
    35

    Discussion

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

    Loading discussion…