What It Means for the Bound to Be Sharp
A general upper bound on a graph's chromatic number is useful even when it is not exact. The maximum-degree-plus-one bound says that a nonempty finite simple graph \(G\) can be properly colored with at most \(\Delta(G)+1\) colors. In this tutorial, we examine two families where this upper bound is attained: complete graphs and odd cycles. In each family, we will compute the maximum degree and the chromatic number, and verify that the two quantities satisfy \(\chi(G)=\Delta(G)+1\).
A proper vertex coloring assigns a color to each vertex so that adjacent vertices receive different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in any proper coloring of \(G\). The degree \(\deg(v)\) of a vertex \(v\) is the number of its neighbors, and \(\Delta(G)\) is the largest degree among the vertices.
The bound itself follows by ordering the vertices and coloring them one at a time. When a vertex is reached, at most \(\Delta(G)\) of its colors are unavailable because of already-colored neighbors. Among \(\Delta(G)+1\) available color labels, at least one therefore remains. This argument proves an upper bound; it does not say every graph needs that many colors. The examples below show that equality does occur.
Complete Graphs Attain Equality
The complete graph \(K_n\) has \(n\) vertices, with an edge between every pair of distinct vertices. Thus every vertex has degree \(n-1\), so \(\Delta(K_n)=n-1\). Also, every pair of vertices is adjacent, forcing all \(n\) vertices to receive different colors in a proper coloring. Assigning one distinct color to each vertex uses \(n\) colors, so \(\chi(K_n)=n\).
Proof. For \(n\ge1\), each vertex of \(K_n\) is adjacent to the other \(n-1\) vertices, giving \(\Delta(K_n)=n-1\). Since every two distinct vertices are adjacent, a proper coloring must assign a different color to each vertex, so at least \(n\) colors are necessary. Giving every vertex its own color is a proper coloring with \(n\) colors, and hence \(\chi(K_n)=n\). Therefore \(\chi(K_n)=n=(n-1)+1=\Delta(K_n)+1\). This also covers \(K_1\), whose sole vertex has degree zero and needs one color. \(\square\)
Worked Example: The Complete Graph \(K_4\)
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). These are all six pairs of distinct vertices, so this is \(K_4\).
Vertex \(1\) is incident with \(12,13,14\), so \(\deg(1)=3\). Vertex \(2\) is incident with \(12,23,24\), so \(\deg(2)=3\). Vertex \(3\) is incident with \(13,23,34\), so \(\deg(3)=3\). Vertex \(4\) is incident with \(14,24,34\), so \(\deg(4)=3\). Thus \(\Delta(G)=3\), and the bound gives \(\Delta(G)+1=3+1=4\).
Every pair of vertices is adjacent, so four distinct colors are necessary. Giving vertices \(1,2,3,4\) four different colors is proper, which proves \(\chi(G)=4\). Therefore \(\chi(G)=4=\Delta(G)+1\).
Check: The degree sum is \(3+3+3+3=12\). There are six edges, each incident with two vertices, so \(2|E|=2\cdot6=12\), in agreement with the computed degrees. The coloring uses four colors, and the adjacency of every pair prevents any two of those vertices from sharing a color.
Odd Cycles Attain Equality Too
Complete graphs force many distinct colors because their vertices are pairwise adjacent. Odd cycles give a different kind of example: each vertex has degree only two, yet three colors are necessary. For an odd integer \(2k+1\ge3\), the cycle \(C_{2k+1}\) consists of distinct vertices \(v_0,v_1,\ldots,v_{2k}\) and the edges joining consecutive vertices, together with \(v_{2k}v_0\).
Proof. Each vertex of a cycle with at least three vertices has exactly two distinct neighbors: its predecessor and its successor around the cycle. Hence \(\Delta(C_{2k+1})=2\). To show that two colors cannot suffice, suppose a proper coloring uses at most two colors. The edge \(v_0v_1\) forces \(v_1\) to have a different color from \(v_0\). Continuing along the cycle, each edge \(v_iv_{i+1}\) forces the color to alternate. Therefore \(v_i\) has the same color as \(v_0\) for even \(i\), and a different color for odd \(i\). The index \(2k\) is even, so \(v_{2k}\) has the same color as \(v_0\), contradicting the edge \(v_{2k}v_0\). Thus at least three colors are needed.
For a coloring with three colors, give \(v_0,v_1,\ldots,v_{2k-1}\) alternating colors \(A,B\), starting with \(A\) at \(v_0\), and give \(v_{2k}\) a third color \(C\). Consecutive vertices among \(v_0,\ldots,v_{2k-1}\) have different colors. Because \(2k-1\) is odd, \(v_{2k-1}\) has color \(B\), while \(v_{2k}\) has color \(C\). The closing edge \(v_{2k}v_0\) joins colors \(C\) and \(A\). Thus every edge has differently colored endpoints, so three colors suffice. Consequently \(\chi(C_{2k+1})=3=2+1=\Delta(C_{2k+1})+1\). \(\square\)
Worked Example: The Five-Cycle
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Each vertex has two incident edges: \(1\) is incident with \(12,51\); \(2\) with \(12,23\); \(3\) with \(23,34\); \(4\) with \(34,45\); and \(5\) with \(45,51\). Hence every degree is two and \(\Delta(G)=2\), so the bound is \(\Delta(G)+1=2+1=3\).
Assign colors in the order \(1,2,1,2,3\) to vertices \(1,2,3,4,5\). On edges \(12,23,34,45,51\), respectively, the endpoint colors are \(1\)-\(2\), \(2\)-\(1\), \(1\)-\(2\), \(2\)-\(3\), and \(3\)-\(1\). Each pair differs, so this is a proper coloring with three colors.
If only two colors were used, the colors would have to alternate along \(1,2,3,4,5\). The sequence would force vertices \(1\) and \(5\) to have the same color, but \(51\) is an edge. Thus two colors cannot suffice, and \(\chi(G)=3=\Delta(G)+1\).
Check: The degree sum is \(2+2+2+2+2=10\), and the five listed edges contribute \(2\cdot5=10\) incidences. This independently checks the degrees. The explicit coloring proves the upper bound of three colors, and the forced alternation proves the matching lower bound.
Worked Example: The Seven-Cycle
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,34,45,56,67,71\}\). Each vertex has two neighbors: vertex \(1\) has \(2,7\); vertex \(2\) has \(1,3\); vertex \(3\) has \(2,4\); vertex \(4\) has \(3,5\); vertex \(5\) has \(4,6\); vertex \(6\) has \(5,7\); and vertex \(7\) has \(6,1\). Therefore \(\Delta(G)=2\), and \(\Delta(G)+1=2+1=3\).
Use the color sequence \(1,2,1,2,1,2,3\) on vertices \(1,2,3,4,5,6,7\). The edges \(12,23,34,45,56,67,71\) have endpoint color pairs \(1\)-\(2\), \(2\)-\(1\), \(1\)-\(2\), \(2\)-\(1\), \(1\)-\(2\), \(2\)-\(3\), and \(3\)-\(1\), respectively. Every edge has differently colored endpoints.
Two colors cannot suffice: alternating from vertex \(1\) along \(1,2,3,4,5,6,7\) forces vertices \(1\) and \(7\) to have the same color, contrary to the edge \(71\). Hence \(\chi(G)=3=\Delta(G)+1\).
Check: The sum of the seven degrees is \(7\cdot2=14\). The seven edges contribute \(2\cdot7=14\) incidences, confirming that the listed cycle gives degree two at every vertex. The explicit three-coloring and the two-color contradiction establish the chromatic number from above and below.
Sharpness Is Not the Same as Equality for Every Graph
These families show that the bound cannot be reduced as a universal statement: complete graphs and odd cycles need exactly \(\Delta(G)+1\) colors. They do not show that every graph needs that many. For example, a path can have maximum degree two while requiring only two colors.
Worked Example: A Path Where the Bound Is Not Sharp
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). The degrees are \(\deg(1)=1\), \(\deg(2)=2\), \(\deg(3)=2\), and \(\deg(4)=1\), so \(\Delta(G)=2\) and the bound is \(\Delta(G)+1=2+1=3\).
Color vertices \(1,3\) with color \(A\), and vertices \(2,4\) with color \(B\). The edge list has endpoint colors \(A\)-\(B\), \(B\)-\(A\), and \(A\)-\(B\), so the coloring is proper. At least two colors are required because \(12\) is an edge. Therefore \(\chi(G)=2\), which is strictly less than \(\Delta(G)+1=3\).
Check: The degree sum is \(1+2+2+1=6\), equal to \(2|E|=2\cdot3=6\). The coloring uses two colors, and the edge \(12\) rules out one color; thus the stated chromatic number is exact.
A common mistake is to read “at most \(\Delta(G)+1\)” as “exactly \(\Delta(G)+1\).” For the path above, the incorrect calculation would be \(\chi(G)=\Delta(G)+1=2+1=3\). The correction is to distinguish the upper bound from the actual minimum: the displayed proper coloring uses two colors, and an edge forces at least two, so \(\chi(G)=2\). Equality must be established with both a coloring using \(\Delta(G)+1\) colors and a reason fewer colors cannot work, as in the complete-graph and odd-cycle proofs.
The examples also show two different mechanisms behind sharpness. In \(K_n\), every pair of vertices is adjacent, so all vertices need distinct colors. In an odd cycle, the obstruction is the closing edge: alternating two colors along all but that edge would assign the same color to its endpoints. In both cases, checking the degree alone gives the upper bound, while the structure of the edges proves the necessary lower bound.
Check Your Understanding
For each question, use the definitions and arguments in the tutorial to justify the conclusion.
- For \(K_6\), compute the degree of each vertex and its chromatic number. Does it attain the maximum-degree-plus-one bound?
- Explain why alternating two colors around an odd cycle forces a conflict at the closing edge.
- Give a proper three-coloring of \(C_9\) by alternating two colors on all but one vertex and assigning a third color to that vertex.
- A graph has maximum degree four and a proper coloring using three colors. What does this tell you about whether the maximum-degree-plus-one bound is sharp for that graph?
- Why does a coloring with \(\Delta(G)+1\) colors alone not prove that \(\chi(G)=\Delta(G)+1\)?