 Chromatic index

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.