Comparing Edge-Coloring Number and Maximum Degree
A proper edge-coloring assigns colors to edges so that edges sharing a vertex receive different colors. At a vertex of degree \(d\), this already requires \(d\) different colors. Thus the maximum degree gives a lower bound for the edge-chromatic number \(\chi'(G)\). Some graphs reach that bound; others require one more color. This tutorial defines those two cases and identifies them directly for paths, cycles, and complete graphs through order five.
Throughout, graphs are finite and simple. A proper edge-coloring is an assignment of colors to the edges such that any two distinct edges with a common endpoint have different colors. The edge-chromatic number \(\chi'(G)\) is the smallest number of colors in a proper edge-coloring of \(G\). A color class is a set of edges receiving one color; it is a matching, meaning that no two of its edges share an endpoint. The maximum degree is denoted by \(\Delta(G)\).
The edge-chromatic number exists for every finite graph: assigning a different color to every edge is a proper coloring, so there is at least one finite number of colors that works. If \(G\) has no edges, then \(\chi'(G)=0\) and \(\Delta(G)=0\), so it is class one.
The Degree Lower Bound
Proof. If \(G\) has no edges, both quantities are zero. Otherwise, choose a vertex \(v\) of maximum degree, so \(\deg(v)=\Delta(G)\). The \(\Delta(G)\) edges incident with \(v\) are pairwise adjacent, and therefore must all receive different colors in any proper edge-coloring. Such a coloring uses at least \(\Delta(G)\) colors. Taking the minimum over proper edge-colorings gives \(\chi'(G)\geq\Delta(G)\). \(\square\)
To prove that a graph is class one, it is therefore enough to exhibit a proper coloring with \(\Delta(G)\) colors. To prove that it is class two, one must show both that \(\Delta(G)\) colors cannot suffice and that \(\Delta(G)+1\) colors do suffice. The lower bound alone does not prove either upper bound. For general simple graphs, Vizing’s theorem is the standard result that rules out a third possibility; its proof belongs to later material. Here, the classifications are established directly for the graph families under discussion.
Paths and Cycles
For a path \(P_n\) on \(n\) vertices, the single-vertex case \(P_1\) has no edges and is class one. When \(n\geq2\), its edges can be listed in order as \(e_1,e_2,\ldots,e_{n-1}\). Color the odd-indexed edges with color 1 and the even-indexed edges with color 2. Consecutive edges receive different colors, and nonconsecutive edges do not share an endpoint. For \(n=2\), only color 1 is needed; for \(n\geq3\), the maximum degree is 2 and both colors are needed at an internal vertex. Thus every path is class one.
For a cycle \(C_n\), \(n\geq3\), the maximum degree is 2. If \(n\) is even, alternating colors 1 and 2 around the cycle gives a proper coloring, so the degree lower bound proves \(\chi'(C_n)=2\). If \(n\) is odd, alternating just two colors around the cycle cannot work: after an odd number of edges, the last edge would have the same color as the first, although those edges meet. Alternating colors 1 and 2 on the first \(n-1\) edges and giving the final edge color 3 gives a proper coloring. Hence \(\chi'(C_n)=3\) for odd \(n\).
Worked Example: A Path on Five Vertices
Let \(G=P_5\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45\}\). The degrees are \(\deg(1)=1\), \(\deg(2)=2\), \(\deg(3)=2\), \(\deg(4)=2\), and \(\deg(5)=1\). Thus \(\Delta(G)=2\).
Color \(12\) and \(34\) with color 1, and color \(23\) and \(45\) with color 2. At vertex 2 the incident edges have colors 1 and 2; at vertex 3 they have colors 2 and 1; at vertex 4 they have colors 1 and 2. The endpoint vertices have only one incident edge each. This is a proper coloring with two colors. The degree lower bound gives \(\chi'(G)\geq2\), so \(\chi'(G)=2=\Delta(G)\).
Check: the coloring uses exactly two colors, and the two edges incident with vertex 3 have different colors. Thus it meets the lower bound and is class one.
Worked Example: An Odd Cycle
Let \(G=C_5\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\). Every vertex has degree 2, so \(\Delta(G)=2\). Color \(12\) and \(34\) with color 1; color \(23\) and \(45\) with color 2; and color \(51\) with color 3.
At vertex 1, the incident edges \(12\) and \(51\) have colors 1 and 3. At vertex 2, the colors are 1 and 2; at vertex 3, they are 2 and 1; at vertex 4, they are 1 and 2; at vertex 5, they are 2 and 3. Every pair of incident edges therefore has distinct colors. The coloring uses three colors.
Two colors cannot suffice: starting with color 1 on \(12\), properness forces \(23\) to have color 2, \(34\) to have color 1, \(45\) to have color 2, and then \(51\) to have color 1. But \(51\) meets \(12\), so those two edges cannot both have color 1. Therefore \(\chi'(G)=3=\Delta(G)+1\), and \(C_5\) is class two.
Check: the exhibited coloring uses three colors, while the forced alternation shows that two colors are impossible. These bounds agree exactly.
Small Complete Graphs
In a complete graph \(K_n\), every pair of distinct vertices is joined by an edge, and each vertex has degree \(n-1\). The small cases show how a counting lower bound and an explicit coloring can work together. In particular, at a given vertex, all incident edges must receive distinct colors; also, each color class can contain only disjoint edges.
Worked Example: The Complete Graphs \(K_1\), \(K_2\), and \(K_3\)
For \(K_1\), \(V=\{1\}\) and \(E=\varnothing\). Hence \(\Delta(K_1)=0\) and \(\chi'(K_1)=0\); it is class one.
For \(K_2\), \(V=\{1,2\}\) and \(E=\{12\}\). Its maximum degree is 1, and its single edge can be colored with one color. Thus \(\chi'(K_2)=1=\Delta(K_2)\), so \(K_2\) is class one.
For \(K_3\), \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\). Each vertex has degree 2. Any two distinct edges of \(K_3\) share a vertex, so each edge must have a different color. This gives the lower bound of three colors, and assigning one color to each of the three edges achieves it. Therefore \(\chi'(K_3)=3=2+1=\Delta(K_3)+1\), so \(K_3\) is class two.
Check: the edge counts are \(0\), \(1\), and \(3\), respectively. The colorings use \(0\), \(1\), and \(3\) colors, in agreement with the values just obtained.
Worked Example: The Complete Graphs \(K_4\) and \(K_5\)
First let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Every vertex has degree 3, so \(\Delta(G)=3\). Use the following three color classes:
Color 1: \(\{12,34\}\); color 2: \(\{13,24\}\); color 3: \(\{14,23\}\). In each class the two edges are disjoint, so this is a proper edge-coloring. It uses three colors, and the degree lower bound requires at least three. Thus \(\chi'(K_4)=3=\Delta(K_4)\), and \(K_4\) is class one. The six edges are counted independently as \(2+2+2=6\).
Now let \(G=K_5\), with \(V(G)=\{0,1,2,3,4\}\) and \(E(G)\) consisting of all ten pairs of distinct vertices: \(01,02,03,04,12,13,14,23,24,34\). Every vertex has degree 4, so \(\Delta(G)=4\). Each color class is a matching and therefore contains at most two edges: three disjoint edges would require six distinct endpoints, but \(K_5\) has only five vertices. With four colors, at most \(4\cdot2=8\) edges could be colored. Since \(K_5\) has ten edges, at least five colors are required.
Five colors suffice. Use these classes:
- Color 1: \(\{14,23\}\).
- Color 2: \(\{02,34\}\).
- Color 3: \(\{13,04\}\).
- Color 4: \(\{24,01\}\).
- Color 5: \(\{03,12\}\).
Each class consists of two disjoint edges, so the coloring is proper. Listing its edges gives \(14,23,02,34,13,04,24,01,03,12\), which is exactly the ten-edge set, with no repetition. Therefore \(\chi'(K_5)=5=4+1=\Delta(K_5)+1\), and \(K_5\) is class two.
Check: the coloring has \(5\cdot2=10\) edges, matching the independently listed ten edges of \(K_5\). The lower bound from the matching sizes rules out four colors, so the five-color construction is optimal.
Using the Class Labels Correctly
The degree lower bound is a necessary condition on every proper edge-coloring, not a complete method for finding one. To establish class one, an explicit coloring must use exactly \(\Delta(G)\) colors. To establish class two, one must rule out \(\Delta(G)\) colors and exhibit a coloring using \(\Delta(G)+1\). The examples above supply both parts of that reasoning.
Common mistake: treating the degree lower bound as an exact answer. For \(K_5\), the maximum degree is 4, so the lower bound says only \(\chi'(K_5)\geq4\). Concluding \(\chi'(K_5)=4\) from that inequality is not justified. In fact, each color class has at most two edges, and four colors can cover at most \(4\cdot2=8\) of the graph’s ten edges. The correction is to use this additional obstruction to prove that four colors fail, then give the five-coloring above. It follows that \(\chi'(K_5)=5\), not 4.
These classifications also illustrate why parity can matter: even cycles admit an alternating two-coloring that closes consistently, while odd cycles do not. For complete graphs, the available size of a matching constrains how many edges each color can cover. In each case, a useful classification requires both a lower-bound argument and a coloring that reaches the proposed number.
Check Your Understanding
For each question, distinguish a lower bound from a completed proof of the edge-chromatic number.
- Why must the edges incident with a vertex of degree \(\Delta(G)\) receive \(\Delta(G)\) distinct colors?
- Classify \(P_1\) and \(P_6\). State both \(\Delta\) and \(\chi'\) in each case.
- Give a two-coloring of \(C_6\), and explain why the same alternating pattern cannot color \(C_5\).
- For \(K_4\), list three disjoint-edge color classes and explain why they prove the edge-chromatic number is 3.
- Why can no color class in \(K_5\) contain three edges? Use this fact to rule out a four-coloring.