Edge colouring

Definition

Let $G$ be a graph with edge set $E$, and let $C$ be a set of colours. An edge colouring of $G$ is a function $c : E \to C$ such that $c(e) \neq c(e')$ for any two distinct edges $e$ and $e'$ with a common end. The chromatic index $\chi'(G)$ is the smallest number of colours in an edge colouring of a finite graph $G$.

Remarks

Each colour class is a matching. Thus an edge colouring is a partition of the edges into matchings. The edges at a vertex need different colours, so $\chi'(G) \ge \Delta(G)$. Vizing's theorem of 1964 says that a simple graph has $\chi'(G) = \Delta(G)$ or $\chi'(G) = \Delta(G) + 1$.

Explanations

L1 human

An edge colouring colours the lines instead of the points: lines that meet must have different colours. In a sports schedule, each colour is a round, and each team plays at most one game per round.