Coloring Along a Path and Around a Cycle
Paths and cycles are among the simplest graphs, but they show why the structure of a graph matters when finding its chromatic number. Along a path, two colors can alternate from one vertex to the next. A cycle has the same sequence of consecutive edges, but also has a closing edge from the last vertex back to the first. When the cycle has odd length, that final edge prevents the alternating two-color pattern from working.
Throughout, graphs are finite and simple. A proper vertex coloring assigns a color to each vertex so that the endpoints of every edge receive different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in a proper coloring of \(G\). We use the standard path \(P_n\) on \(n\ge 1\) vertices and cycle \(C_n\) on \(n\ge 3\) vertices:
Thus \(P_1\) has one vertex and no edges. The cycle \(C_n\) has the edges of the path through \(v_1,\ldots,v_n\), plus the edge \(v_nv_1\). To color vertices in sequence, we will use color labels \(1\), \(2\), and, when needed, \(3\). The labels themselves have no significance; only whether adjacent vertices receive different labels matters.
The Chromatic Number of a Path
Proof. If \(n=1\), the graph has one vertex and no edges. Giving that vertex color \(1\) is a proper coloring, so \(\chi(P_1)\le 1\). A coloring of a nonempty graph must assign a color to its vertex, so zero colors cannot suffice. Hence \(\chi(P_1)=1\).
Now let \(n\ge2\). Give \(v_i\) color \(1\) when \(i\) is odd and color \(2\) when \(i\) is even. Every edge of \(P_n\) is \(v_iv_{i+1}\); one of \(i,i+1\) is odd and the other is even, so its endpoints receive different colors. Therefore \(\chi(P_n)\le2\). The path contains the edge \(v_1v_2\), whose endpoints must receive different colors in any proper coloring. Thus \(\chi(P_n)\ge2\), and \(\chi(P_n)=2\). \(\square\)
The lower-bound argument is local: a single edge rules out a one-color coloring. The upper-bound argument works for every edge because the color changes at each step along the path. Together they certify the exact chromatic number, rather than merely providing a coloring.
Worked Example: The One-Vertex Path and a Six-Vertex Path
First, let \(P_1\) have \(V=\{v_1\}\) and \(E=\varnothing\). Assign color \(1\) to \(v_1\). There are no edges to check, so this is proper. Because the graph has a vertex, a coloring needs at least one color. Thus \(\chi(P_1)=1\).
Now let \(P_6\) have \(V=\{v_1,v_2,v_3,v_4,v_5,v_6\}\) and \(E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6\}\). Assign colors \(1,2,1,2,1,2\), in that order. Checking each edge gives: \(v_1v_2\) has colors \(1,2\); \(v_2v_3\) has \(2,1\); \(v_3v_4\) has \(1,2\); \(v_4v_5\) has \(2,1\); and \(v_5v_6\) has \(1,2\). Every edge has differently colored endpoints.
Check: the edge \(v_1v_2\) requires at least two colors, and the displayed assignment uses two. Therefore \(\chi(P_6)=2\), in agreement with the theorem.
The Chromatic Number of a Cycle
Proof. Every cycle has an edge, so no cycle can be colored with only one color. If \(n\) is even, color \(v_i\) with color \(1\) for odd \(i\), and color \(2\) for even \(i\). Each edge \(v_iv_{i+1}\) for \(1\le i<n\) joins consecutive indices of opposite parity and therefore has differently colored endpoints. Since \(n\) is even, \(v_n\) has color \(2\), whereas \(v_1\) has color \(1\); thus the closing edge \(v_nv_1\) is proper too. This gives \(\chi(C_n)\le2\). The cycle has an edge, so \(\chi(C_n)\ge2\), proving \(\chi(C_n)=2\).
Now suppose \(n\) is odd, so \(n=2k+1\) for some integer \(k\ge1\). First, two colors do not suffice. If a proper coloring used at most two colors, the edge \(v_1v_2\) would require two different colors; call them \(a\) and \(b\), with \(v_1\) colored \(a\) and \(v_2\) colored \(b\). Along each successive edge, the next vertex must take the other of these two colors. Therefore every odd-indexed vertex has color \(a\) and every even-indexed vertex has color \(b\). In particular, \(v_n=v_{2k+1}\) has color \(a\), the same as \(v_1\). But \(v_nv_1\) is an edge, contradicting properness. Hence \(\chi(C_n)\ge3\).
For an upper bound, color \(v_i\) with color \(1\) for odd \(i\) and color \(2\) for even \(i\), for \(1\le i\le 2k\), and give \(v_{2k+1}\) color \(3\). The edges among \(v_1,\ldots,v_{2k}\) join consecutive indices, so their endpoints have different colors. The two remaining edges are \(v_{2k}v_{2k+1}\), whose endpoint colors are \(2\) and \(3\), and \(v_{2k+1}v_1\), whose colors are \(3\) and \(1\). Both are proper. This gives \(\chi(C_n)\le3\); combined with the lower bound, \(\chi(C_n)=3\). \(\square\)
The distinction is exactly the closing edge. Alternation always works on the consecutive edges \(v_1v_2,\ldots,v_{n-1}v_n\). For an even cycle, the last vertex gets the color different from \(v_1\), so the closing edge also works. For an odd cycle, that last vertex gets the same color as \(v_1\), and a third color repairs the conflict.
Worked Example: An Even Cycle \(C_8\)
Let \(C_8\) have \(V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8\}\) and \(E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6,v_6v_7,v_7v_8,v_8v_1\}\). Assign colors \(1,2,1,2,1,2,1,2\), respectively.
For the first seven edges, the endpoint color pairs in order are \((1,2),(2,1),(1,2),(2,1),(1,2),(2,1),(1,2)\), each pair containing distinct colors. The closing edge \(v_8v_1\) has endpoint colors \(2\) and \(1\), so it is proper as well. This is a two-coloring. Since \(C_8\) has the edge \(v_1v_2\), one color cannot suffice.
Check: the coloring uses two colors and the edge \(v_1v_2\) gives a lower bound of two. Therefore \(\chi(C_8)=2\).
Worked Example: An Odd Cycle \(C_7\)
Let \(C_7\) have \(V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\) and \(E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6,v_6v_7,v_7v_1\}\). Assign colors \(1,2,1,2,1,2,3\), respectively.
Check the edges in the listed order. Their endpoint color pairs are \((1,2),(2,1),(1,2),(2,1),(1,2),(2,3),(3,1)\). Each pair has distinct entries, including the pair on the closing edge \(v_7v_1\). Thus three colors suffice.
To check that two colors do not suffice, start with \(v_1\) colored \(1\). The edge \(v_1v_2\) forces \(v_2\) to have color \(2\); continuing to alternate forces \(v_3,v_4,v_5,v_6,v_7\) to have colors \(1,2,1,2,1\). Then \(v_7v_1\) joins two vertices of color \(1\), which is not proper. A one-color coloring also fails because \(v_1v_2\) is an edge. Therefore at least three colors are required.
Check: the displayed assignment is proper and uses three colors, while the closing-edge argument rules out two or fewer. Hence \(\chi(C_7)=3\).
Common Pitfall: Forgetting the Closing Edge
A common error is to alternate two colors around an odd cycle, check only the edges \(v_1v_2,\ldots,v_{n-1}v_n\), and conclude that the cycle is two-colorable. For example, on the \(C_7\) above, alternating gives \(1,2,1,2,1,2,1\). The first six edges are properly colored, but the last edge \(v_7v_1\) has colors \(1\) and \(1\). The correction is to check every edge in the cycle, including \(v_nv_1\). For an odd cycle, give \(v_n\) color \(3\); then its two incident cycle edges have color pairs \((2,3)\) and \((3,1)\).
These formulas are useful because they provide both a construction and a certificate of optimality. The alternating assignments show that the stated numbers of colors suffice. An edge rules out one color for paths with at least two vertices and for all cycles; the forced alternation around an odd cycle rules out two. No search over all possible colorings is needed.
Check Your Understanding
For each question, distinguish the coloring construction from the argument that fewer colors cannot work.
- What is \(\chi(P_1)\), and why can the one-vertex path not use zero colors?
- Give a proper two-coloring of \(P_5\) by listing the color of each vertex, and identify an edge that proves one color is insufficient.
- Explain why alternating two colors gives a proper coloring of \(C_6\), including its closing edge.
- Why does alternating two colors fail on \(C_9\), even though it colors each edge \(v_iv_{i+1}\) properly?
- Describe a three-coloring of \(C_5\) and state which two edges must be checked after coloring \(v_1,\ldots,v_4\) alternately.