---
tag: B99049JPY6
kind: statement
role: theorem
name: Vizing's theorem
msc: [05C15]
uses: [0JD5C82QMB, 02CDYWSWSY, 0KNAN9F27P]
about: [02CDYWSWSY]
sources:
  - url: https://en.wikipedia.org/wiki/Vizing's_theorem
same_as:
  wikidata: Q2226822
  wikipedia: Vizing's theorem
---

## Statement

Let $G$ be a finite simple [[graph|0JD5C82QMB]] with [[maximum degree|0KNAN9F27P]] $\Delta$.
Let $\chi'(G)$ be the chromatic index of $G$, the least number of colours in a proper [[edge colouring|02CDYWSWSY]] of $G$.
Then
$$\Delta \le \chi'(G) \le \Delta + 1.$$

## Remarks

The lower bound is clear: the $\Delta$ edges at a vertex of maximum degree need distinct colours.
The upper bound is proved by colouring the edges one at a time with $\Delta + 1$ colours.
When a new edge cannot be coloured, a fan of edges at one end and a path in two colours are recoloured to free a colour.
Graphs with $\chi' = \Delta$ are of class 1, and graphs with $\chi' = \Delta + 1$ are of class 2.
An odd cycle has $\Delta = 2$ and needs $3$ colours, so it is of class 2; every bipartite graph is of class 1, by a theorem of Kőnig.
The hypothesis that $G$ is simple is needed: the multigraph on three vertices with each pair joined by $k$ parallel edges has $\Delta = 2k$ but needs $3k$ colours.
Deciding whether a graph is of class 1 is NP-complete.

## Explanations

### L1 human

Colour the edges of a graph so that edges at the same vertex get different colours.
If some vertex has $\Delta$ edges, you need at least $\Delta$ colours.
Vizing's theorem says that one extra colour is always enough.

### L2 human

For vertex colouring, the chromatic number can be far above any simple lower bound, but for edge colouring Vizing's theorem pins the answer to two values.
The proof is constructive and gives an efficient algorithm for a colouring with $\Delta + 1$ colours.
For multigraphs, Vizing also proved $\chi' \le \Delta + \mu$, where $\mu$ is the largest number of parallel edges.