Codex @codex  0

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.

An $r$-regular graph is class two when its edge chromatic number exceeds $r$. For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly $r+1$. An $r$-colour proper edge colouring of an $r$-regular graph would partition its edges into $r$ perfect matchings, since every vertex would see each colour exactly once.

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.

A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.

Vizing's theorem states that a finite simple graph of maximum degree $\Delta$ satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree $\Delta$ require different colours.

Hall's marriage theorem states that a finite bipartite graph with vertex sets $A,B$ has a matching in a graph saturating $A$ if and only ifwhere $N(S)\subseteq B$ is the graph neighbourhood of $S$. Here matching saturation means that each vertex of $A$ is incident with an edge of the matching in a graph; it does not require every vertex of $B$ to be met.

The Vizing theorem states that for every finite simple graph of maximum vertex degree $\Delta$, its edge chromatic number satisfies $\boxed{\Delta \le {\chi }^{\prime }(G)\le \Delta +1}$. The lower bound follows because all edges incident to a maximum-degree vertex need different colors. The simplicity hypothesis matters: unrestricted multigraphs need not satisfy this upper bound.

Vizing theorem states that every finite simple graph of maximum degree $\Delta$ haswhere ${\chi }^{\prime }(G)$ is its edge chromatic number. The lower bound follows because all edges incident with a vertex of degree $\Delta$ need different colours.

For the upper bound, induct on the number of edges. Delete an edge $xy$ and colour the remaining graph with the palette $\{1,\dots ,\Delta +1\}$. We use the Vizing fan lemma: in a partial proper edge colouring with one uncoloured edge $xy$, if the palette has one more colour than the maximum degree, a sequence of fan rotations and two-colour Kempe-chain interchanges makes some colour missing at both ends of the uncoloured edge.

Here is the fan argument. Build a maximal sequence $y_0=y,y_1,\dots ,y_k$ of distinct neighbours of $x$ such that, for $i\ge 1$, the colour on $x{y}_i$ is missing at an earlier fan vertex. Rotating an initial fan segment means moving each colour on $x{y}_i$ to the preceding edge where it is missing; this preserves properness and moves the uncoloured edge to the end of that segment. Choose a colour $\alpha$ missing at $x$ and a colour $\beta$ missing at $y_k$. On the maximal $\alpha$-$\beta$ alternating path from $y_k$, interchange $\alpha$ and $\beta$. If the path does not reach $x$, $\alpha$ is then missing at both $x$ and $y_k$, so rotate the fan and colour its final uncoloured edge $\alpha$. If it reaches $x$, its last edge at $x$ has colour $\beta$. Maximality of the fan forces the other endpoint of that edge to be a fan vertex; rotate up to that vertex first. This breaks the alternating path before $x$, reducing to the preceding case. This proves the fan lemma and extends the colouring to $xy$, completing the induction.

For $K_{n,n}$, label both vertex classes by $\mathbb{Z}/n\mathbb{Z}$ and colour edge $(i,j)$ by $i+j$. Each colour is a perfect matching, so this is an $n$-edge-colouring. Since $\Delta (K_{n,n})=n$, ${\chi }^{\prime }(K_{n,n})=n$. If $r=\max \{m,n\}$, embed $K_{m,n}$ into $K_{r,r}$ and restrict its $r$-edge-colouring. The degree lower bound then gives

Finally, subdividing one edge of $K_{n,n}$ produces $n^2+1$ edges on $2n+1$ vertices while keeping maximum degree $n$. In any proper edge colouring, each colour class is a matching of size at most $n$. An $n$-edge-colouring could therefore colour at most $n^2$ edges, a contradiction. Thus ${\chi }^{\prime }(G)>n$, while Vizing theorem gives ${\chi }^{\prime }(G)\le n+1$, so

The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colors in a proper coloring of edges, where incident edges receive distinct colors. Hall marriage theorem says a bipartite graph has a matching saturating one side exactly when $|N(S)|\ge |S|$ for every subset $S$ of that side.

In a 4-regular bipartite graph, the $4|S|$ edges leaving $S$ all enter $N(S)$, whose vertices can receive at most $4|N(S)|$ such edges. Hence Hall's condition holds and there is a perfect matching. Remove it and repeat in the resulting 3-, 2-, and 1-regular bipartite graphs. The four perfect matchings give a four-edge-coloring, while every vertex requires four distinct colors. Therefore

Every vertex has degree three, so its incident edges require three distinct colours. Three suffice by colouring an edge according to which of the three coordinates changes; every vertex has exactly one edge of each coordinate type. Thus the edge chromatic number is three.

A triangle $x_1{y}_1{y}_2$ forces at least three vertex colours. Three suffice: colour $x_1,x_2$ blue; $y_1,y_3,y_4$ orange; and $y_2,y_5$ green, as in the drawing. Hence the chromatic number is three.

The five edges incident to $x_1$ force at least five edge colours. An explicit proper five-edge-colouring is

Give $y_1{y}_2$ colour 5 and $y_1{y}_5$ colour 3. At $y_1$ the incident colours are $1,2,5,3$; at $y_2$ they are $2,3,5$; at $y_5$ they are $5,1,3$; all are distinct. The two remaining vertices each have two distinct incident colours. Thus the edge chromatic number is five.