Edge chromatic number (${\chi }^{\prime }(G)$)

The edge chromatic number is the least number of colours required to colour edges so that incident edges receive different colours.

An $r$-regular graph with $r\ge 2$ and a bridge in a graph separating an odd number of vertices from the rest cannot have an $r$-colour proper edge colouring. Such a colouring would partition the edges into $r$ perfect matchings. Each perfect matching must cross the odd-sided cut of a graph, so each would have to contain its unique crossing edge, the bridge in a graph. An edge cannot belong to two colour classes.

For odd $r$, every bridge in a graph in an $r$-regular graph automatically has odd-sized sides: if $S$ is either resulting connected component of a graph, double counting gives $r|S|=2|E(S)|+1$, so parity forces $|S|$ odd. Thus an odd-$r$ regular graph with a bridge in a graph is a class two regular graph.

For every finite bipartite graph, the edge chromatic number equals its maximum degree. Repeatedly remove a matching covering maximum-degree vertices in a bipartite graph: each removal reduces the maximum degree by at least one. The removed matchings in a graph are colour classes of a proper edge colouring. The reverse bound follows from the distinct colours required at a vertex of maximum degree.

Every finite simple graph of maximum degree $\Delta$ has edge chromatic number $\Delta$ or $\Delta +1$.

In a partial proper edge colouring with one uncoloured edge incident with a vertex $x$, a Vizing fan is a sequence of neighbours of $x$ whose incident edge colours are missing at earlier fan vertices. With one more colour than the maximum degree, fan rotations and a two-colour Kempe chain free one common colour at the endpoints of the uncoloured edge.