Colored graphs
Lax119563.ColoredGraphs · concepts/Lax119563/ColoredGraphs.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A colored graph consists of a finite vertex set , an edge set , and a vertex coloring . All graphs are simple and undirected, and every vertex has exactly one color.
We take for the number of vertices of , and use the natural numbers as the set of colors . Thus any two colored graphs use the same set of colors and can be compared.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Combinatorics.SimpleGraph.Basic |
| 2 | import Mathlib.SetTheory.Cardinal.Finite |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Colored graphs |
| 7 | type: definition |
| 8 | --- |
| 9 | A *colored graph* consists of a finite vertex set , |
| 10 | an edge set , and a vertex coloring |
| 11 | . All graphs are simple and undirected, and every |
| 12 | vertex has exactly one color. |
| 13 | |
| 14 | We take for the number of vertices of , and use the |
| 15 | natural numbers as the set of colors . Thus any two colored graphs use the |
| 16 | same set of colors and can be compared. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax119563.ColoredGraphs |
| 20 | |
| 21 | /-- A *colored graph* on the vertex set `{0, …, n-1}`, with colors in `ℕ`. -/ |
| 22 | structure 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. -/ |
| 31 | noncomputable def ColoredGraph.numEdges (G : ColoredGraph) : ℕ := |
| 32 | Nat.card G.graph.edgeSet |
| 33 | |
| 34 | end Lax119563.ColoredGraphs |
| 35 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments