Edge Coloring Paths and Cycles
In a proper vertex coloring, adjacent vertices must receive different colors. For edge coloring, the corresponding requirement is local to each vertex: edges that meet at a vertex must receive different colors. Paths and cycles are simple enough that their exact edge-chromatic numbers can be found directly, but they reveal an important distinction. Alternating two colors works around every even cycle, while on an odd cycle that alternation fails precisely when it returns to the starting edge.
All graphs in this tutorial are finite and simple. A path \(P_n\) has \(n\) vertices in a linear sequence, with an edge between each consecutive pair; thus it has \(n-1\) edges. A cycle \(C_n\), for \(n\ge 3\), has \(n\) vertices in cyclic order and an edge between each consecutive pair, including the last and first vertices; it has \(n\) edges.
Edges that do not meet may share a color. Equivalently, the edges of any one color form a matching: no two of them have a common endpoint. In particular, if a vertex has degree \(d\), its \(d\) incident edges require \(d\) distinct colors. Therefore every graph with at least one edge satisfies \(\chi'(G)\ge \Delta(G)\), where \(\Delta(G)\) is its maximum degree.
The Exact Formulas
Proof. First consider paths. The graph \(P_1\) has no edges, so its edge-chromatic number is \(0\) by definition. The graph \(P_2\) has one edge, which can be colored with one color; since it has an edge, zero colors cannot color it, so \(\chi'(P_2)=1\).
Now let \(n\ge 3\). Write the vertices of \(P_n\) in order as \(v_1,\dots,v_n\), and let \(e_i=v_iv_{i+1}\) for \(1\le i\le n-1\). Give \(e_i\) color 1 when \(i\) is odd and color 2 when \(i\) is even. The only pairs of distinct edges that meet are consecutive edges \(e_i,e_{i+1}\). Their indices have opposite parity, so their colors differ. This is a proper coloring with two colors. Every internal vertex has degree 2, so its two incident edges must have different colors, giving \(\chi'(P_n)\ge 2\). The construction gives the reverse inequality, hence \(\chi'(P_n)=2\).
Next let \(C_n\) be a cycle, with vertices \(v_1,\dots,v_n\) in cyclic order and edges \(e_i=v_iv_{i+1}\) for \(1\le i<n\), together with \(e_n=v_nv_1\). If \(n\) is even, color \(e_i\) with color 1 for odd \(i\) and color 2 for even \(i\). Consecutive edges along the sequence have different colors. The remaining pair to check is \(e_n,e_1\): because \(n\) is even, \(e_n\) has color 2 and \(e_1\) has color 1. Thus this is a proper two-coloring. Every cycle vertex has degree 2, so at least two colors are necessary. It follows that \(\chi'(C_n)=2\) for even \(n\).
Finally suppose \(n\) is odd. Two colors cannot properly color \(C_n\). Indeed, if \(e_1\) has color 1, then properness forces \(e_2\) to have color 2, \(e_3\) to have color 1, and so on. Since \(n\) is odd, \(e_n\) is forced to have color 1, the same color as \(e_1\). But \(e_n\) and \(e_1\) meet at \(v_1\), a contradiction. One color is also impossible because adjacent edges would have the same color, and a cycle has adjacent edges. Hence at least three colors are needed.
For an upper bound, color \(e_1,\dots,e_{n-1}\) alternately with colors 1 and 2, beginning with color 1, and give \(e_n\) color 3. Consecutive edges among \(e_1,\dots,e_{n-1}\) have different colors. The last edge \(e_n\), colored 3, differs from both \(e_{n-1}\) and \(e_1\). These are all the pairs of distinct edges that meet, so the coloring is proper and uses three colors. Thus \(\chi'(C_n)=3\) when \(n\) is odd. \(\square\)
The lower bounds in this proof have two sources. A vertex of degree 2 forces at least two colors, while an odd cycle has an additional global obstruction: alternation around the cycle cannot close consistently. The explicit patterns show that these lower bounds are attained in every case.
Worked Example: A Path with Five Edges
Let \(G=P_6\), with vertex set \(V(G)=\{1,2,3,4,5,6\}\) and edge set \(E(G)=\{12,23,34,45,56\}\). Find \(\chi'(G)\) and give an optimal coloring.
The path has \(n=6\) vertices, so its number of edges is \(n-1=6-1=5\), in agreement with the five edges listed. Its endpoints 1 and 6 have degree 1, and its internal vertices 2, 3, 4, and 5 have degree 2. Thus \(\Delta(G)=2\), so at least two colors are required. The path formula also gives \(\chi'(P_6)=2\), since \(6\ge3\).
In order along the path, assign the colors as follows:
| Edge | 12 | 23 | 34 | 45 | 56 |
|---|---|---|---|---|---|
| Color | 1 | 2 | 1 | 2 | 1 |
At vertex 2, the incident edges 12 and 23 have colors 1 and 2. At vertex 3, edges 23 and 34 have colors 2 and 1; at vertex 4, edges 34 and 45 have colors 1 and 2; and at vertex 5, edges 45 and 56 have colors 2 and 1. The endpoints have only one incident edge each. Therefore the coloring is proper and uses two colors.
Check: the displayed coloring proves \(\chi'(G)\le2\), while vertex 2 has two incident edges, which must have different colors, proving \(\chi'(G)\ge2\). Together these give \(\chi'(G)=2\).
Worked Example: An Even Cycle
Let \(G=C_8\), with vertex set \(V(G)=\{1,2,3,4,5,6,7,8\}\) and edge set \(E(G)=\{12,23,34,45,56,67,78,81\}\). Find and verify an optimal edge-coloring.
This cycle has \(n=8\) vertices and \(8\) listed edges, as the cycle formula gives. Since 8 is even, the theorem gives \(\chi'(C_8)=2\). Color the edges in cyclic order alternately, starting with color 1:
| Edge | 12 | 23 | 34 | 45 | 56 | 67 | 78 | 81 |
|---|---|---|---|---|---|---|---|---|
| Color | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
At vertices 2 through 8, each pair of incident edges appears consecutively in the table and has different colors. The wraparound pair at vertex 1 is 81, of color 2, and 12, of color 1, so it also satisfies the rule. Every vertex has degree 2, which rules out a one-color edge-coloring; the displayed coloring proves two colors suffice.
Check: the table assigns one color to each of the \(8\) listed edges. Each vertex has one incident edge of color 1 and one of color 2, including vertex 1, so the coloring is proper. Therefore \(\chi'(C_8)=2\).
Worked Example: An Odd Cycle
Let \(G=C_5\), with vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,34,45,51\}\). Find the minimum number of colors and construct a coloring that achieves it.
The graph has \(n=5\) vertices and \(5\) listed edges. Since 5 is odd, the theorem gives \(\chi'(C_5)=3\). The lower bound can also be checked directly: if edges 12 and 23 use colors 1 and 2, properness forces 34 to use 1 and 45 to use 2. Edge 51 meets 45, so it cannot use 2; but it also meets 12, so it cannot use 1. A third color is necessary.
Use the following assignment:
| Edge | 12 | 23 | 34 | 45 | 51 |
|---|---|---|---|---|---|
| Color | 1 | 2 | 1 | 2 | 3 |
At vertex 1, edges 51 and 12 have colors 3 and 1. At vertex 2, edges 12 and 23 have colors 1 and 2; at vertex 3, edges 23 and 34 have colors 2 and 1; at vertex 4, edges 34 and 45 have colors 1 and 2; and at vertex 5, edges 45 and 51 have colors 2 and 3. All incident pairs have different colors, so the assignment is proper.
Check: all \(5\) listed edges are colored, and the five vertex checks cover every pair of incident edges in \(C_5\). The construction uses three colors, while the forced alternation argument shows two cannot suffice. Hence \(\chi'(C_5)=3\).
Reading the Patterns and Avoiding a Common Error
For a path, the edge sequence has two ends, so alternating colors has no closing condition. A path with at least two edges needs two colors because its internal vertices have degree 2, and the alternating pattern meets that requirement. The path with just one edge is different: its maximum degree is 1, so one color suffices. The one-vertex path has no edges at all, so the stipulated value is zero.
For a cycle, every vertex has degree 2, but that local fact only gives a lower bound of two. Whether two colors suffice depends on the cycle length. Alternating colors around the cycle works exactly when the final edge has a different color from the first. This happens for even cycles; in an odd cycle the final and first edges are forced to match if only two colors are used.
Common mistake: alternating around an odd cycle without checking the final pair. On \(C_5\), coloring 12, 23, 34, 45 alternately gives colors 1, 2, 1, 2. Continuing the same alternation assigns color 1 to 51. That is not a proper coloring: edges 51 and 12 both have color 1 and meet at vertex 1. The correction is not to overlook that pair: a third color on 51 resolves the conflict, and the odd-cycle lower-bound argument proves that no two-color adjustment can avoid it.
These exact computations are useful as small test cases for edge-coloring arguments. They distinguish the maximum-degree lower bound from the extra obstruction created by an odd cycle, without requiring any general edge-coloring theorem. The patterns also give immediate constructions: alternate along a path, alternate around an even cycle, and alternate on all but one edge of an odd cycle before assigning that last edge a third color.
Check Your Understanding
For each question, justify the number of colors by giving both a lower bound and a coloring, unless the question asks for a proof.
- What is \(\chi'(P_1)\), and why does the maximum-degree lower bound not require a positive number of colors in this case?
- Give a proper edge-coloring of \(P_7\) using two colors. Which vertices show that one color cannot suffice?
- Explain why alternating two colors around \(C_6\) satisfies the condition at the edge joining the last vertex back to the first.
- Why does an alternating two-color assignment fail on \(C_7\), even though it works along the first six edges?
- Give a three-color pattern for an odd cycle \(C_n\), and identify the two edges whose conflict is avoided by assigning the third color.