Chromatic index
= Chromatic index
{title2=$\chi\prime(G)$}
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>.<Graph Theory by Reinhard Diestel>[Colouring, author-hosted chapter preview, p. 124: chromatic index and line graph]{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)\geq\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>.
\Image[/edge-coloring-triangle-even-cycle.png]
{title=Worked <proper edge colourings>: a <triangle in a graph> needs three colours, while an even <cycle graph> needs two}
{description=Numbers beside <edges> are colour labels; letters at dots are <vertices>. Both <graphs> have <maximum degree of a graph> two. The <triangle in a graph> has three pairwise conflicting <edges>, while opposite <edges> of the square can share a colour.}
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\geq2$. On an <odd cycle> $C_{2m+1}$, $m\geq1$, 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.